Height of a Binary tree : Recursive and Iterative Approach

Problem : Given a Binary Tree , find the height of the tree. 

 Example:

Height of above Tree = 3

Explanation:

 Height of a binary tree is  the number of nodes along the longest path from the root node down to the farthest leaf node. The Height of the empty tree is 0, the Height of the tree in the above example is 3

Solution : 

There can be two approach to solve this problem : 

1. Recursive : using recursive calls to find heights of left and right subtress 

2. Iterative : using level order traversal 

Let us have a look at both the approaches one by one : 

A. Recursive Solution :  

   1. if the root ==null , return 0

Else : perform 2 -->4

   2. find height of left subtree , say LH 

   3. find height of right subtree , say RH

   4. if LH >RH, return LH +1 , else return RH+1

B. Iterative Solution :

 Do a level order traversal, increment height at each level. Return height at the end.

Implementation : 

Following are the java implementations for both solutions 

A. RECURSIVE :

 int height(Node root){

        

         if(root==null) return 0;

       

       else{

            int lh= height(root.left);

            int rh= height(root.right);

       

       if(lh>rh) return lh+1;

       else return rh+1;

       }

          

    }

B. ITERATIVE :

 int height(Node root)

    {

         if(root==null) return 0;

       Node node=root;

       int height=0;

       Queue<Node> q= new LinkedList<Node>();

       q.add(node);

       

       while(true){

            // nodeCount (queue size) indicates number of nodes

            // at current lelvel.

            int nodeCount = q.size();

            if (nodeCount == 0) {

                return height;

            }

            height++;

            // Dequeue all nodes of current level and Enqueue all

            // nodes of next level

            while (nodeCount > 0) {

                Node newnode = q.peek();

                q.remove();

                if (newnode.left != null) {

                    q.add(newnode.left);

                }

                if (newnode.right != null) {

                    q.add(newnode.right);

                }

                nodeCount--;

            }

        }

           

           

           

       }

    

________________________________________________________________________________

REFERENCES : 

http://cslibrary.stanford.edu/110/BinaryTrees.html

https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree

Least Common Ancestor : Binary Tree

Lowest Common Ancestor:

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor (Djidjev, Pantziou & Zaroliagis 1991). In ontologies, the lowest common ancestor is also known as the least common subsumer.

In a tree data structure where each node points to its parent, the lowest common ancestor can be easily determined by finding the first intersection of the paths from vand w to the root. In general, the computational time required for this algorithm is O(h) where h is the height of the tree (length of longest path from a leaf to the root). However, there exist several algorithms for processing trees so that lowest common ancestors may be found more quickly. Tarjan's off-line lowest common ancestors algorithm, for example, preprocesses a tree in linear time to provide constant-time LCA queries. In general DAGs, similar algorithms exist, but with super-linear complexity.

[SOURCE: https://en.wikipedia.org/wiki/Lowest_common_ancestor]

Problem :

Given a binary tree and two values d1& d2, find the least common ancestor of the two values in the input tree.


Example:
  Consider the following image :

Solution :
We follow a recursive approach where in we recurse through the right and left children of the parameter node .

Return value is root itself if output of each recursion is null , else the we return the value is which in non-null among the two recursive output.

Base and Edge cases are as shown in the code.

Implementation:

Binary Tree Node :

public class BinaryTreeNode {

    private int data;    private BinaryTreeNode left;    private BinaryTreeNode right;
    public int getData() {
        return data;    }

    public void setData(int data) {
        this.data = data;    }

    public BinaryTreeNode getLeft() {
        return left;    }

    public void setLeft(BinaryTreeNode left) {
        this.left = left;    }

    public BinaryTreeNode getRight() {
        return right;    }

    public void setRight(BinaryTreeNode right) {
        this.right = right;    }
}

LCA class : 

public class LCA {


    public BinaryTreeNode getLCA(BinaryTreeNode root, int data1, int data2){

    //Base case
        if (root == null){
            return  null;        }

    //edge case
        if (root.getData()==data1 || root.getData() == data2) {
            return root;        }


    BinaryTreeNode leftLCA = getLCA(root.getLeft(), data1, data2);            BinaryTreeNode rightLCA = getLCA(root.getRight(), data1, data2);

    if (leftLCA != null && rightLCA != null){
        return root;    }

    if (leftLCA == null) {
        return rightLCA;    }

    else {
        return leftLCA;    }


    }
}

Reverse a singly linked list : Recursively

Following approach can be followed to reverse a singly linked list recursively



Approach : 

1.Divide the list in two parts : first and rest.
2.Recursively call the reverse method with rest.
3.link rest-->first
4.fix the last node

Implementation: 


public node reverse(Node head){

if( head==null) return;

Node first= head;
Node rest= first.next;

if(rest== null) return;

reverse(rest); //recursively call reverse for the rest .

first.next.next= first;// next now points to current

first.next = null; //fix the last node

head= rest;

return head;

}

Complexity :

Time: O(n)
Space: O(1)