How to print a subtree of a binary tree?

Question

In my program, I have initialized a binary tree and I want to search if a node exists in that binary tree. If it does exist, then I will print the subtree of that node and the level it was found. I am able to perform my search method but I am not sure how to print the subtree of that node found and its level.

For example, this is my binary tree [K=3 L=[K=1 R=[K=2]] R=[K=5 L=[K=4]]. If I search for node 1, then it will return the node (not null) since it exists in my binary tree.

Problem: I need to print only the subtree of the node and the level where it was found: [K=1 R=[K=2]], level=1.

Here is my source code for reference:

Main Class

// instantiate BST object
BST<Character> bst = new BST<>(); 

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

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

    bst1.insert(c);
}

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

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

for (int i = 0; i < letter2.length; i++) {
    Character c = letter2[i];
    
    if (bst1.search(c) != null) { // if found, print the node (w/ subtree) and its level
        // ** part that should print the subtree and its level
    }
    else {
        System.out.println(c + " is not found.");
    }
}

BST Class - where my search method is declared

public class BST<T extends Comparable<T>> extends BT<T> {
    // insert() method

    // search method
    public BTNode<T> search(T k) {// my method
        
            BTNode<T> n = root;
            
            while (n != null) {
                if (n.info.compareTo(k) == 0)  {
                    return n;
                }
                else {
                    if (n.info.compareTo(k) > 0) {
                        n = n.left;
                    }
                    else {
                        n = n.right;
                    }
                }
            }
            return null;
        }
}

Thanks in advance!

Answer 1

I did not modify your code. Instead, I used an imaginary class Node that I've written. Also, I have written all of them as half pseudo half java code. Suppose your node has only one int type variable and two children.

class Node{
    int data;
    Node left;
    Node right;
}

You have a printExistingSubTree method in your BST class that does the what you exactly ask for:

printExistingSubTree(Node node, int key):
    if (find(node.left, key, 0) != -1)
        then 
            printTree(node.left)
            print(find(node.left, key, 0))
    if (find(node.right, key, 0) != -1)
        then printTree(node.right)
            printTree(node.right)
            print(find(node.right, key, 0))

You have a find method in your BST class that does find the index:

int find(Node node,int key, int level)
    if(node.data is equal to the key)
        then return level
    int left = -1;
    
    if(node.leftChild is not null)
        then left = find(node.left, key, level+1)
    if(left != -1)
        return left
    int right = -1;
    if(node.rightChild is not null)
        then right = find(node.right, key, level+1)
    return right

Then, to print, you should decide how you want to traverse the subtree.

You have a printTree method in your BST class that prints the subtree in postorder:

void printTree(Node node){
    if (node == null)
        return;
     printTree(node.left);
 
     printTree(node.right);
 
     print(node.data + " ");
}

Note: I did not understand your whole code. Therefore, I have just written the answer of your question in the pseudo code format. I think, you can write your own code from that.

Note2: There may be some typos&wrong namings. PLease do not lynch. Just write in the comments and I'll correct.