'Subtree points to wrong root (traversal)

I have made a program that inserts nodes to a binary tree and then using a search method to check if a node exists in the created binary tree or not. If it exists, I have to print the subtree of the node searched and its level. It is able to produce the correct subtrees for some nodes but it is not able to do so for other nodes. I also have difficulty in handling generics.

Here is my expected output:

ht=5 [K=G L=[K=D L=[K=B] R=[K=E]] R=[K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]]] // created binary tree

G [K=G L=[K=D L=[K=B] R=[K=E]] R=[K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]]], level=0 
T [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=1
D [K=D L=[K=B] R=[K=E], level=1 
Q [K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S], level=2
B [K=B], level=2
L [K=L L=[K=H] R=[K=N L=[K=M]]], level=3
E [K=E], level=2
N [K=N L=[K=M]], level=4
S [K=S], level=3
M [K=M], level=5
H [K=H], level=4

Then here is my output:

ht=5 [K=G L=[K=D L=[K=B] R=[K=E]] R=[K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]]] // created binary tree

G [K=G L=[K=D L=[K=B] R=[K=E]] R=[K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]]], level=0 // correct subtree
T [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=1 // correct subtree
D [K=D L=[K=B] R=[K=E], level=1 // correct subtree
Q [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=2
B [K=D L=[K=B] R=[K=E], level=2
L [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=3
E [K=D L=[K=B] R=[K=E], level=2
N [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=4
S [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=3
M [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=5
H [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=4

Problem: as you can see, it is not able to produce the correct starting K (root) for the nodes starting at level=2

Here is my code for reference: Main Class

BST<Character> bst1 = new BST<>(); 

// insert values to bst1
String str = "GTDQBLENSMH";
char[] letter = str.toCharArray();

for (int i = 0; i < letter.length; i++) {
    Character c = letter[i];
    bst1.insert(c);
}

// print bst1
System.out.println("\nht=" + bst1.findHeight(bst1.root) + " " + bst1.toString() + "\n");

// search values in bst1 
String str2 = "GTDQBLENSMH"; 
char[] letter2 = str2.toCharArray();

for (int i = 0; i < letter2.length; i++) {
    Character c = letter2[i];
    
    if (bst1.search(c) != null) { // if found
    
        System.out.println(c + " "); 
        bst1.printExistingSubTree(bst1.root, c);
    }
    else {                      // if not found
        System.out.println(c + " is not found.");
    }
}

BST<T extends Comparable> extends BT Class

    // insert(), findHeight(), search() methods
    // prints the subtree with its level
    public BTNode<T> printExistingSubTree(BTNode<T> node, T k) {            
        if (find(node.left, k, 1) != -1) {
            printTree(node.left);
            System.out.println("\b" + ", level=" + find(node.left, k, 1));
            return node.left;
        }
        if (find(node.right, k, 1) != -1) {
            printTree(node.right);
            System.out.println("\b" + ", level=" + find(node.right, k, 1));
            return node.right;
        } else {
            printTree(node);
            System.out.println("\b" + ", level=0");
        }
        return null;
    }
    
    // find the level
    public int find(BTNode<T> node, T k, int level) {
        if(node.info.compareTo(k) == 0) {
            return level;
        }
        
        int left = -1;
        
        if(node.left != null) {
            left = find(node.left, k, level + 1);
        }
        
        if(left != -1) {
            return left;
        }
        
        int right = -1;
        
        if(node.right != null) {
            right = find(node.right, k, level + 1);
        }
        
        return right;
    }
    
    // creates the subtree
    public void printTree(BTNode<T> node)
    {
        if (node == null) {
            return;
        }

        if (node != null) {
            System.out.println("\b[K=" + node.info);
            
            if (node.left != null) {
                System.out.println("\b L=");
                printTree(node.left);
                System.out.println("\b]");
            }
            if (node.right != null) {
                System.out.println("\b R=");
                printTree(node.right);
                System.out.println("\b]");
            }
        }
    }

BTNode Class

public class BTNode<T> {
    T info;
    int level;
    BTNode<T> left, right;

    public BTNode(T el) {
        this(el, null, null);
    }
    
    public BTNode(T el, BTNode<T> l, BTNode<T> r) {
        info = el;
        left = l;
        right = r;
    }
}

BT Class

public class BT<T> {
    BTNode<T> root = null;
    int height = 0;
    
    public BT() {
        BTNode<T> node = new BTNode("");
    }
    
    public void setRoot(BTNode<T> n) {
        this.root = n;
    }
    
    public String toString() {
        return toString(root);
    }
    
    public String toString(BTNode<T> n) {
        String s = "";
        
        if (n == null) {
            return "";
        }
        
        if (n != null) {
            s = "[K=" + n.info;
            
            if (n.left != null) {
                s = s + " L=" + toString(n.left) + "]";
            }
            if (n.right != null) {
                s = s + " R=" + toString(n.right) + "]";
            }
        }
        return s;
    }
}


Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source