Leave a comment

Find height of a binary tree iteratively.

To solve this kind of problem, first try to figure out how would you solve if it is given on copy in pictorial format. Let say a tree is given as given below and we need to calculate the height of the tree, how would you do that? It is as simple as that, we will traverse each branch and calculate the length of all the branches. Length of the longest branch will be the height of the tree. Same approach we will follow.
So, we’ll start from root and will go deeper in tree to calculate the length of each branch. Let’s say given tree is as follows:

tree2
We will apply the above approach as follows:

We will start from root which is 1 and will keep this node somewhere for future processing. At the same time we will maintain the length of the branch we are traversing. At this point of time we have just visited root node, the length of the current branch will be zero. Now, it’s left exist and not yet processed so, will jump to its left which is 2 and length of the branch will become 1 then will jump to 4 and length will become 2 and so on. Traversal is done as follows

      1–>2—>4–>8

After 8 there is neither left nor right so, 8 is a leaf node and we are done with our first branch. We are ended with 3 as length of our current branch. We have to find out the length of longest branch and at this point of time we are not sure if our current branch is longest or not so we will maintain maxLength which will hold the length of the longest branch we have already explored so that at the end maxLength will give the length of the longest branch. As of now, we have just explored our very first branch so maxLength will hold 3, the length of our first branch. Now, suppose if there is a right child of 4 say 10 so we need to go back till 4 and then move rightwards. As we are already holding nodes of the current branch we have 1–>2–>4–>8. Now we will go back to 4 and will move rightwards and will end up with 1–>2–>4–>10, length 3. we will compare length against maxLength to check if current branch is longest, if so, will assign the value of length to maxLength otherwise maxLength will be as is. Now we are done with both the branch which is left and right of 4 and will go back to 2.

Now here comes the questions, where we will store the information of current branch so that once we reach at leaf or while going backward after processing nodes, we can go back to the previous node and can check if the right child exist of that node. This kind of situation is usually called post decision problem and stack is the best choice for that. So, as soon as we visit a node, we will store it in stack and once we are done with a node (need to go backward) we will remove it from top and next top will be the node need to be considered next.

Here the new question comes, what are the information stored by stack node. Let’s think about it, first thing which is stored by stack is the current tree node under consideration and what else? If you will read the story written back, each time we are jumping leftwards first , but who’s left ? left of the node we have just visited and how will you find out which node is just visited? isn’t it the top of the stack? yeah it is. So our algorithm says we will check if left of the node we just visited exists, jump to its left, but what if you have already processed it’s left? for example you first reached to 8 which is leaf and then 8 got removed from stack and you reached back to 4 and now you will find oh left of 4 exist, jump again on 8 which is already processed. To prevent this scenario stack node will maintain another information isLeftVisited which will tell if the left node is already processed or not and algorithm is modified, we will move to its left, only if left exist and not yet visited. Another information stored by the stack node is isRightVisited for the same reason as with isLeftVisited.

Here you go for implementation:

The class name preceded by BST because we have written it for Binary Search Tree. However, iterativeHeight method doesn’t consider any tree property if it is a binary search tree or just binary tree so, it will work for binary tree as well.

public class BSTNode {
    private int val;
    private BSTNode left;
    private BSTNode right;
    public BSTNode(int val) {
        super();
        this.val = val;
    }
    public int getVal() {
        return val;
    }
    public void setVal(int val) {
        this.val = val;
    }
    public BSTNode getLeft() {
        return left;
    }
    public void setLeft(BSTNode left) {
        this.left = left;
    }
    public BSTNode getRight() {
        return right;
    }
    public void setRight(BSTNode right) {
        this.right = right;
    }
}


public class BSTUtils {
    public static int iterativeHeight(BSTNode root){
        if(root == null)
            return 0;
        if(root.getLeft() == null && root.getRight() == null)
            return 0;
        int height = 0;
        int heightOfCurrentBranch = 0;
        class StackNode{
            BSTNode node;
            boolean isLeftVisited;
            boolean isRightVisited;
            StackNode(BSTNode node){
                this.node = node;
            }
        };
        Stack stk = new Stack();
        stk.push(new StackNode(root));
        while(!stk.isEmpty()){
            if(stk.peek().node.getLeft() != null && !stk.peek().isLeftVisited){
                stk.peek().isLeftVisited = true;
                stk.push(new StackNode(stk.peek().node.getLeft()));
                heightOfCurrentBranch++;
                continue;
            }
            if(stk.peek().node.getRight() != null && !stk.peek().isRightVisited){
                stk.peek().isRightVisited = true;
                stk.push(new StackNode(stk.peek().node.getRight()));
                heightOfCurrentBranch++;
                continue;
            }
            if(heightOfCurrentBranch > height)
                height = heightOfCurrentBranch;
            heightOfCurrentBranch--;
            stk.pop();
        }
        return height;
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: