Thursday, 26 December 2013

Deepest left leaf node in a binary tree

Question : 

Given a Binary Tree, find the deepest leaf node that is left child of its parent. For example, consider the following tree. The deepest left leaf node is the node with value 9.

Code:


 public class DeepestLeftLeafNodeFinder {

    Node deepestNode;
    int deepestNodeDepth;

    public Node findDeepestLeftLeafNode(Node root,boolean isLeftNode,int depth){

        if(isLeftNode){
            if(depth > deepestNodeDepth){
                deepestNode = root;
                deepestNodeDepth = depth;
            }
        }

        if(root.getLeft() != null){
            findDeepestLeftLeafNode(root.getLeft(),true,depth + 1);
        }

        if(root.getRight() != null){
            findDeepestLeftLeafNode(root.getRight(),false,depth+1);
        }

        return deepestNode;
    }
}

Test :

    public static void main(String args[]){

        Node root = new Node(1);

        Node l = new Node(2);
        root.setLeft(l);
        Node r = new Node(3);
        root.setRight(r);

        Node l1 = new Node(4);
        l.setLeft(l1);

        Node r1 = new Node(5);
        r.setLeft(r1);
        Node r2 = new Node(6);
        r.setRight(r2);

        Node r12 = new Node(7);
        r1.setRight(r12);

        Node r121 = new Node(9);
        r12.setLeft(r121);

        Node r22 = new Node(8);
        r2.setRight(r22);

        Node r222 = new Node(10);
        r22.setRight(r222);

        System.out.println("Deepest left node of the tree is : " +
                new DeepestLeftLeafNodeFinder().findDeepestLeftLeafNode(root,false,0).getValue());
    }

Output :

Deepest left node of the tree is : 9 

Note : Complexity of above code is O(N) as we are visiting each node at most once. Do let me know if anyone has a better solution.

1 comment:

  1. This comment has been removed by the author.

    ReplyDelete

t> UA-39527780-1 back to top