Incrementing Height Variable in Binary Search Tree-CodePudding

I am trying to use an iterative method to calculate the height of my binary search tree, but I am having trouble figuring out when to add 1 to my height variable, aka when there is a new level of nodes. Here is my insertion method:

public Node insertRec(Node x, String key) {
        if (x == null)
        {
            x = new Node(key);              // if bst is empty, add new node and return
            height  ;
            return x;
        }

        if (key.compareTo(x.key) < 0) {         
            x.left = insertRec(x.left, key);    // recursive calls to find correct spot to insert in the tree
        }
        else if (key.compareTo(x.key) > 0) {
            x.right = insertRec(x.right, key);
        }   
        return x;                                       // returns unchanged node
    }

As you can see, right now I am just adding 1 to the height when a new node is added and then I use another method to just return that variable, but that is not a correct number for the height. I believe I need some sort of test so that if there is a new level of nodes, then 1 is added to the height, but I'm not sure where to start with that.

CodePudding user response：

An easy solution for your case is to add an height variable to your function, then you can compute the maxHeight after the Node creation:



public Node insertRec(Node x, String key, int newHeight) {
        if (x == null)
        {
            x = new Node(key);              
            if (newHeight > maxHeight) 
                maxHeight = newHeight;

            return x;
        }

        if (key.compareTo(x.key) < 0) {         
            x.left = insertRec(x.left, key,   newHeight);    // recursive calls to find correct spot to insert in the tree
        }
        else if (key.compareTo(x.key) > 0) {
            x.right = insertRec(x.right, key,   newHeight);
        }   
        return x;                                       // returns unchanged node
    }

CodePudding user response：

If you use a recursive call it is quite easy:

public int getHeight(Node x)
{
    int height = 0;
    if(x.left != null)
        height = Math.max(height, getHeight(x.left);
    if(x.right != null)
        height = Math.max(height, getHeight(x.right);
    
    return height   1;
}

But since you want an iterative method, you need to implement a stack yourself and keep a map of the current values:

public int getHeight(Node root)
{
    HashMap<Node, Integer> heights = new HashMap<>();
    Stack<Node> toVisit = new Stack<>();
    toVisit.push(root);
    
    while(!toVisit.isEmpty())
    {
        Node x = toVisit.peek(); // Before removing the node from the stack, check that his children have been already visited
        
        if(x.left != null && !heights.containsKey(x.left))
        {
            //Left node has not been visited yet
            toVisit.push(x.left);
            continue;
        }
        if(x.right != null && !heights.containsKey(x.right))
        {
            //Right node has not been visited yet
            toVisit.push(x.right);
            continue;
        }
        int height = 0;
        if(x.left != null)
            height = Math.max(height, heights.get(x.left));
        if(x.right != null)
            height = Math.max(height, heights.get(x.right));
        
        heights.put(x, height   1);
        toVisit.pop(); //Remove node x from the stack, it has been successfully visited
     }

     return heights.get(root);
}

Nota: I didn't test the code