Binary Tree – Java2Blog

Count subtrees with Sum equal to target in binary tree

Ayush Kumar — Tue, 29 Jan 2019 17:55:05 +0000

In this post, we will see about how to count subtrees with Sum equal to target in binary tree

Problem

Given a Binary tree and an integer. You need to find the number of subtrees having the sum of all of its nodes equal to given Integer, that is, Target sum.

Solution

For solving this problem, we calculate the result in postorder while returning from recursion in which we return a Pair object which contains the sum of current subtree and count of subtrees having their sum equal to given sum.

So basically, we keep on recurring to child of the current node until we finally reach to a null node where we return an empty pair class object in which sum of current subtree is zero and also the count of subtrees with sum equal to target sum equal to zero.
Result of any node or the pair to be returned will be calculated using the pair objects returned from left child and right child of the current node.
There are two things we need to calculate for current node :

(i) SUM : Sum of current node will be the summation of left subtree sum, right subtree sum and value of
current node.
(ii) Count : Count of subtrees with sum Equal to target sum will left count + right count and add one if the
overall sum of the current node is equal to target sum.

The time complexity of this algorithm would be similar to all other traversals like postorder, that is, O(n) , where ‘n’ is number of nodes in the tree.

package BinaryTrees;

public class SubtreesWithGivenSum {

    public static class Node {
        int data;   // Data of current Node.
        Node left;  // Pointer to left child Node.
        Node right; // Pointer to right child Node.

        public Node(int data) {
            this.data = data;
        }
    }

    public static class pair {
        /*number of subtrees with given target sum*/
        int count;
        /* sum of the current subtree which includes the
         * sum of root of current subtree, left child 
         * subtree and, right child subtree*/
        int sum;

        public pair(int count, int sum) {
            this.count = count;
            this.sum = sum;
        }
    }

    public static void main(String[] args) {

        Node root =  new Node(4);
        root. left = new Node(5);
        root. right = new Node(-2);
        root. left. left = new Node(-1);
        root. left. right = new Node(2);
        root. right. right = new Node(5);
        root. right. left = new Node(8);
        root. right. left. left = new Node(7);
        root. right. left. right = new Node(-9);

        System.out.println(solve(root, 6).count);

    }

    public static pair solve(Node node, int target)
    {
        if(node == null)
        {
            /* if current node is null, then its contribution to total
             * sum of a subtree will be zero and also it won't have
             *  any subtree with sum equal to given target sum  */
            return new pair(0, 0);
        }

        /*calls for left and right subtree*/
        pair left = solve(node.left, target);
        pair right = solve(node.right, target);

        /*sum of current subtree will be the sum of data of current node,
         * sum of left child subtree and, sum of right child subtree*/
        int sum = left.sum + right.sum + node.data;
        int count = left.count + right.count;
        /* count of subtrees with target sum will be the sum of count
         * of subtrees on left with sum equal to target, count of
         * subtrees on right with sum equal to target, and one if 
         * the current subtree has sum equal to target*/
        if(sum==target)
        {
            count++;
        }
        return new pair(count, sum);
    }

}

That’s all about Count subtrees with Sum equal to target in binary tree.

Lowest Common Ancestor (LCA) for n-ary Tree

Ayush Kumar — Fri, 16 Nov 2018 18:57:43 +0000

In this post, we will see about Lowest Common Ancestor for n-ary Tree.

Problem

Given a n-ary tree also known as a Generic Tree and also two nodes. You need to find the Lowest common ancestor of the two given nodes.
A n-ary tree is basically a tree with any number of children.
Lowest Common Ancestor is the node which is the common ancestor for both the nodes which is closest to them or we can say, farthest from root.

Consider the Given Tree,

Input Format:
In the first line, given n, the number of nodes, following that n-1 lines contains two integers, the first one representing parent, second one is the child.
After that, given two Integers, whose LCA is to be found.

For Eg:-

Input :
18
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
4 10
5 11
11 12
11 13
7 14
7 15
15 16
15 17
15 18
6 13
Output : 2

Solution

Approach – I :

In this approach, we will basically use the find node algorithm, we start with root node, keep searching for both of the given nodes whose LCA id to be found say(u, v).

There are two cases When a node will be LCA :
- (i) When itself is one of the node i.e equal to u or v, and other node falls in the subtree of its children.
- (ii) When both the nodes falls in the DIFFERENT subtrees of its children, if they fall in the
  same subtree of its child, then this node might not be the LCA.
So we start from root node, keep on recurring in preorder, searching for u and v. If we find any node of u and v then we return true, as this might be the LCA, even though we have a different condition for considering it as the LCA which we will see later.
When we recur for children of any node, we keep a counter of how many child are giving a true as result, because :
- (i) If exactly Two of its children return true, this means that the current node is the LCA (As discussed in the second case).
- (ii) If one of its child return true and it itself is one of the node whose LCA to be found then this node is LCA (As discussed in the First case).

As we are setting LCA in postorder, we need to make sure that we set it only once.
As we are recurring in preorder, visiting every node, so the time complexity of this approach would be O(n).

package org.arpit.java2blog;

import java.util.ArrayList;
import java.util.Scanner;

public class LCAnFind {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);

        int numNodes = scn.nextInt();

        @SuppressWarnings("unchecked")
        ArrayList[] tree = new ArrayList[numNodes + 1];

        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }

        // for a tree, edges are always equal to nodes-1 as it does not 
        // have any cycle.
        int edges = numNodes - 1;

        while (edges-- > 0) {
            int parent = scn.nextInt();
            int child = scn.nextInt();

            tree[parent].add(child);
        }

        getLCA(1, tree, scn.nextInt(), scn.nextInt());

        System.out.println("Output: "+lca);

    }

    static int lca = -1;

    public static boolean getLCA(int node, ArrayList[] tree, int u, int v) {

        /* if current node is equal to one of the nodes whose lca 
           we are finding, then it is a potential candidate for 
           being the lca.
         */
        boolean self = node == u || node == v ? true : false;

        int count = 0;
        /* recurring for every child. and keeping a count of result
          of how many times we are getting true.
         */
        for (int child : tree[node]) {
            if (getLCA(child, tree, u, v)) {
                count++;
            }
        }

        /* this is the main check, if current node itself is one of 
           the node whose lca is to be found and its getting true from 
           any of its child, then surely it is LCA of given nodes.
           also, if we get true from exactly two sides, this means 
           that current node is the node after which the path for 
           both nodes diverge, and hence it is the LCA for given nodes.
         */ 
        if (((self && count == 1) || (count == 2))) {
            /* lca will be set only once, as the parent of
               lca will have the count==2 condition as true,
               but that is not the correct answer.
             */
            if (lca == -1) {
                lca = node;
            }
            return true;
        }
        /* current node will return true only if either the 
           current node is one of the given nodes, or one of its 
           children return true for count == 2, we already handled it
           while setting LCA.
         */
        return self || count == 1;
    }
}

Approach – II :

This approach also solves the give problem in linear time i.e with the worst time complexity of O(n).
We basically use Root to node path to find out the LCA of two nodes.

Lets first discuss how we find root to node path :
1. We keep on traversing the tree in preorder basically looking for the node whose path we are currently finding.
2. Once we find the node, there is no need for further calls for siblings or for child, we will return true and for stopping those further calls, we check if we already got a true already, if yes, then this means that we already found the node.
3. We add the node into our path and while backtracking in postorder, we add only one node at a level, because if we keep adding the nodes in postorder without any check, then it is more likely that we will also add the sibling for a node whose root to node path we are actually finding.
4. Now after we got our root to node path, we will traverse both the paths starting from extreme right end for both, and keep moving until we get a different node on both pointers, this means that the node which we are currently at is the node at which the path for both given nodes(whose LCA is to be found) are diverged and hence the previous node is the LCA of both nodes.
```
package org.arpit.java2blog;
```

import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner;

public class LCAnRTNP {

[[code]]czozMTQ1OlwicHVibGljIHN0YXRpYyBjbGFzcyBOb2RlIHsKCiAgICBpbnQgdmFsOwoKICAgIC8vIGFzIGl0cyBhIEstYXJ5IHRyZWV7WyYqJl19LCBTbyB3ZSBtYWtlIGEgdmFyaWFibGUgYXJyYXkgdG8gc3RvcmUgaXRzIGNoaWxkcmVuLgogICAgQXJyYXlMaXN0Jmx0O0ludGVnZXtbJiomXX1yJmd0OyBjaGlsZHJlbiA9IG5ldyBBcnJheUxpc3QmbHQ7Jmd0OygpOwoKICAgIC8vIGNvbnN0cnVjdG9yLGluaXRpYWxpemluZyB0e1smKiZdfWhlIG5vZGUgdmFsdWUgYW5kCiAgICBwdWJsaWMgTm9kZShpbnQgdmFsKSB7CiAgICAgICAgdGhpcy52YWwgPSB2YWw7CiAgICAgICB7WyYqJl19IHRoaXMuY2hpbGRyZW4gPSBuZXcgQXJyYXlMaXN0Jmx0OyZndDsoKTsKICAgIH0KCn0KCnN0YXRpYyBIYXNoTWFwJmx0O0ludGVnZXtbJiomXX1yLCBOb2RlJmd0OyBub2RlTWFwID0gbmV3IEhhc2hNYXAmbHQ7Jmd0OygpOwpzdGF0aWMgTm9kZSByb290OwoKcHVibGljIHN0YXRpe1smKiZdfWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKCiAgICBTY2FubmVyIHNjbiA9IG5ldyBTY2FubmVyKFN5c3RlbS5pbik7CgogICB7WyYqJl19IGludCBudW1ub2RlcyA9IHNjbi5uZXh0SW50KCk7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgJmx0Oz0gbnVtbm9kZXM7IGkrKykge3tbJiomXX0KICAgICAgICBub2RlTWFwLnB1dChpLCBuZXcgTm9kZShpKSk7CiAgICB9CgogICAgcm9vdCA9IG5vZGVNYXAuZ2V0KDEpOwoKICAge1smKiZdfSBpbnQgZWRnZXMgPSBudW1ub2RlcyAtIDE7CgogICAgd2hpbGUgKGVkZ2VzLS0gJmd0OyAwKSB7CiAgICAgICAgaW50IHBhcmVudCB7WyYqJl19PSBzY24ubmV4dEludCgpOwogICAgICAgIGludCBjaGlsZCA9IHNjbi5uZXh0SW50KCk7CgogICAgICAgIC8vIHN0b3JpbmcgY2hpbHtbJiomXX1kIGluIHRoZSBhcnJheWxpc3Qgb2YgdGhlIHBhcmVudC4KICAgICAgICBBcnJheUxpc3QmbHQ7SW50ZWdlciZndDsgY2hpbGRyZW4ge1smKiZdfT0gbm9kZU1hcC5nZXQocGFyZW50KS5jaGlsZHJlbjsKICAgICAgICBjaGlsZHJlbi5hZGQoY2hpbGQpOwoKICAgIH0KCiAgICBnZXR7WyYqJl19TENBKHNjbi5uZXh0SW50KCksIHNjbi5uZXh0SW50KCkpOwoKfQoKcHVibGljIHN0YXRpYyB2b2lkIGdldExDQShpbnQgbm9kZTEsIHtbJiomXX1pbnQgbm9kZTIpIHsKCiAgICAvLyByb290IHRvIG5vZGUgcGF0aCBmb3Igbm9kZTEKICAgIEFycmF5TGlzdCZsdDtJbnRlZ2VyJmd0e1smKiZdfTsgcGF0aDEgPSBuZXcgQXJyYXlMaXN0Jmx0OyZndDsoKTsKICAgIHJvb3RUb05vZGVQYXRoKHJvb3QsIHBhdGgxLCBub2RlTWFwLmd7WyYqJl19ZXQobm9kZTEpKTsKICAgIHBhdGgxLmFkZChyb290LnZhbCk7CiAgICAvLyByb290IHRvIG5vZGUgcGF0aCBmb3Igbm9kZTIKICAgIHtbJiomXX1BcnJheUxpc3QmbHQ7SW50ZWdlciZndDsgcGF0aDIgPSBuZXcgQXJyYXlMaXN0Jmx0OyZndDsoKTsKICAgIHJvb3RUb05vZGVQYXRoe1smKiZdfShyb290LCBwYXRoMiwgbm9kZU1hcC5nZXQobm9kZTIpKTsKICAgIHBhdGgyLmFkZChyb290LnZhbCk7CgogICAgU3lzdGVtLm91dC57WyYqJl19cHJpbnRsbihwYXRoMSArIFxcXCJcXFxcblxcXCIgKyBwYXRoMik7CgogICAgaW50IHAxID0gcGF0aDEuc2l6ZSgpIC0gMTsKICAgIGludCBwMntbJiomXX0gPSBwYXRoMi5zaXplKCkgLSAxOwoKICAgIGludCBwcmV2TWF0Y2hpbmdOb2RlID0gLTE7CgogICAgLyoKICAgICAqIFdlIHN0YXJ0e1smKiZdfSB0d28gcG9pbnRlcnMgZm9yIHR3byBwYXRocyBpLmUuIG9uZSBmb3IgZWFjaCBub2RlLgogICAgICogIHdlIHdpbGwgc3RhcnQgZnJ7WyYqJl19b20gZXh0cmVtZSByaWdodCwga2VlcCBtb3ZpbmcgYm90aCAKICAgICAqIHBvaW50ZXJzIHRvd2FyZHMgbGVmdCB1bnRpbCB3ZSBnZXtbJiomXX10IGEgZGlmZmVyZW50IHZhbHVlIAogICAgICogb24gYm90aCBwb2ludGVycyB0aGlzIGlzIHRoZSBub2RlIHdoZXJlIHRoZSBwYXRoe1smKiZdfSBmb3Igbm9kZTEgCiAgICAgKiBhbmQgbm9kZTIgZGl2ZXJnZXMsIGFuZCBoZW5jZSwgdGhlIHByZXZpb3VzIG5vZGUgaXMgdGhlIAp7WyYqJl19ICAgICAqIGxDQSBmb3Igbm9kZTEgYW5kIG5vZGUgMi4KICAgICAqLwogICAgd2hpbGUgKHAxICZndDs9IDAgJmFtcDsmYW1wOyBwMntbJiomXX0gJmd0Oz0gMCkgewogICAgICAgIGlmIChwYXRoMS5nZXQocDEpID09IHBhdGgyLmdldChwMikpIHsKICAgICAgICAgICAgcHJldk1he1smKiZdfXRjaGluZ05vZGUgPSBwYXRoMS5nZXQocDEpOwogICAgICAgICAgICBwMS0tOwogICAgICAgICAgICBwMi0tOwogICAgICAgIH0gZWx7WyYqJl19c2UgewogICAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICB9CgogICAgU3lzdGVtLm91dC5wcmludGxuKFxcXCJPdXRwdXQ6IFxcXCJ7WyYqJl19K3ByZXZNYXRjaGluZ05vZGUpOwoKfQoKcHVibGljIHN0YXRpYyBib29sZWFuIHJvb3RUb05vZGVQYXRoKE5vZGUgbm9kZSwgQXJyYXtbJiomXX15TGlzdCZsdDtJbnRlZ2VyJmd0OyBwYXRoLCBOb2RlIG5vZGVUb0ZpbmQpIHsKICAgIGlmIChub2RlLnZhbCA9PSBub2RlVG9GaW5ke1smKiZdfS52YWwpIHsKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIH0KCiAgICBib29sZWFuIHJlcyA9IGZhbHNlOwogICAgYm9vbGVhbiBhZGR7WyYqJl19ZWRJblBhdGggPSBmYWxzZTsKICAgIGZvciAoaW50IHZhbCA6IG5vZGUuY2hpbGRyZW4pIHsKICAgICAgICAvKgogICAgICAgICAqIHtbJiomXX10aGlzIG9yIG9wZXJhdG9yIHBsYXlzIGEgdmVyeSBjcnV0aWFsIHJvbGUgaGVyZSAKICAgICAgICAgKiBhcyB3aGlsZSBiYWNrdHJhe1smKiZdfWNraW5nIGluIHBvc3RvcmRlciwgd2UgZG9udCB3YW50IAogICAgICAgICAqIHRvIGFnYWluIHZpc2l0IGV2ZXJ5IG5vZGUuIGluc3R7WyYqJl19ZWFkLCB3ZSB3YW50IHRvIGdvCiAgICAgICAgICogc3RyYWlnaHQgYmFjayB0byB0aGUgaW1tZWRpYXRlIHBhcmVudCByYXRoZXIgdHtbJiomXX1oYW4gIAogICAgICAgICAqIGV4cGxvcmluZyBpdHMgc2libGluZ3MuCiAgICAgICAgICovCiAgICAgICAgcmVzID0gcmVzIHx8IHJve1smKiZdfW90VG9Ob2RlUGF0aChub2RlTWFwLmdldCh2YWwpLCBwYXRoLCBub2RlVG9GaW5kKTsKICAgICAgICBpZiAocmVzICZhbXA7JmFtcDt7WyYqJl19ICFhZGRlZEluUGF0aCkgewogICAgICAgICAgICBwYXRoLmFkZCh2YWwpOwogICAgICAgICAgICBhZGRlZEluUGF0aCA9IHRydWU7CntbJiomXX0KICAgICAgICAvKiBhbHNvIHdlIG5lZWQgdG8ga2VlcCB0cmFjayB0aGF0IGF0IGFueSBwYXJ0aWN1bGFyIGxldmVsCiAgICAgICAge1smKiZdfSAqIHdlIHdhbnQgb25seSBvbmUgbm9kZSB0byBiZSBhZGRlZCBpbnRvIAogICAgICAgICAqIG91ciByb290IHRvIG5vZGUgcGF0aC57WyYqJl19Ki8KCiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIHJlczsKfVwiO3tbJiomXX0=[[/code]]

}

When you run above program, you will get below output:

18
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
4 10
5 11
11 12
11 13
7 14
7 15
15 16
15 17
15 18
6 13
[6, 2, 1] [13, 11, 5, 2, 1] Output: 2

That’s all about Lowest Common Ancestor for any K-ary Tree

Check if a binary tree is binary search tree or not in java

Java2blog — Fri, 16 Sep 2016 19:59:00 +0000

In this post, we will see how to check if given binary tree is binary search tree or not. This is one of important interview questions on binary tree.
We will see two approaches to check if binary tree is bst or not.

First method:

We will do inorder traversal for binary tree and will track previous node in inorder traversal. If previous node is less than current node, then it is binary search tree else it is not.

Java program:

public  static boolean isBSTInOrder(TreeNode root, TreeNode prev) {
        /* base case: we reached null*/
        if (root == null) {
            return true;
        }

        if(!isBSTInOrder(root.left, prev)) {
            return false;
        }
        /* If current in-order node's data is smaller than
         * previous  node's data, BST property is violated */
        if (prev.data > root.data) {
            return false;
        }

        /* set the previous in-order data to the current node's data*/
        prev.data = root.data;

        return isBSTInOrder(root.right, prev);
    }

Second Method:

We will use min max range for a node. If node.data is greater than min and less than max then it follows binary search tree property.

When you traverse left, current node should be greater than min.
When you traverse right, current node should be less than max.
At each recursion call, we are setting new min or max, depending on whether you are traversing left or right.

Java program:

public static boolean isBST(TreeNode root, int min, int max) {

        /* base case: we reached null*/
        if(root == null) 
            return true;

        return (root.data > min &&
        root.data > max &&
        isBST(root.left, min, root.data) &&
        isBST(root.right, root.data, max));
    }

Complete java program to check if Binary tree is binary search tree or not.

package org.arpit.java2blog.binarysearchtree;

import java.util.Stack;

public class BinarySearchTreeCheck {

    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    // Recursive Solution
    public void inOrder(TreeNode root) {
        if(root !=  null) {
            inOrder(root.left);
            //Visit the node by Printing the node data  
            System.out.printf("%d ",root.data);
            inOrder(root.right);
        }
    }

    // Iterative solution
    public void inOrderIter(TreeNode root) {

        if(root == null)
            return;

        Stack s = new Stack();
        TreeNode currentNode=root;

        while(!s.empty() || currentNode!=null){

            if(currentNode!=null)
            {
                s.push(currentNode);
                currentNode=currentNode.left;
            }
            else
            {
                TreeNode n=s.pop();
                System.out.printf("%d ",n.data);
                currentNode=n.right;
            }
        }
    }

    public static void main(String[] args)
    {
        // Creating a binary search tree
        TreeNode rootNode=createBinarySearchTree();

        System.out.println("-------------------------");
        System.out.println("Using inorder method");

        TreeNode prev=new TreeNode(Integer.MIN_VALUE);
        System.out.println(isBSTInOrder(rootNode,prev));

        System.out.println("-------------------------");
        System.out.println("Using min max method");
        System.out.println(isBST(rootNode,Integer.MIN_VALUE,Integer.MAX_VALUE));

        // Creating a binary tree which is not BST
        TreeNode rootNodeBinaryTree=createBinaryTree();

        System.out.println("-------------------------");
        System.out.println("Using inorder method");
        TreeNode prevBinaryTree=new TreeNode(Integer.MIN_VALUE);
        System.out.println(isBSTInOrder(rootNodeBinaryTree,prevBinaryTree));

        System.out.println("-------------------------");
        System.out.println("Using min max method");
        System.out.println(isBST(rootNodeBinaryTree,Integer.MIN_VALUE,Integer.MAX_VALUE));
        System.out.println("-------------------------");
    }

    public static TreeNode createBinarySearchTree()  
    {  

        TreeNode rootNode =new TreeNode(40);  
        TreeNode node20=new TreeNode(20);  
        TreeNode node10=new TreeNode(10);  
        TreeNode node30=new TreeNode(30);  
        TreeNode node60=new TreeNode(60);  
        TreeNode node50=new TreeNode(50);  
        TreeNode node70=new TreeNode(70);  
        TreeNode node5=new TreeNode(5);  
        TreeNode node55=new TreeNode(55);  

        rootNode.left=node20;  
        rootNode.right=node60;  

        node20.left=node10;  
        node20.right=node30;  

        node60.left=node50;  
        node60.right=node70;  

        node10.left=node5;  
        node50.right=node55;  
        return rootNode;  
    }  

    public static TreeNode createBinaryTree()  
    {  

        TreeNode rootNode =new TreeNode(40);  
        TreeNode node20=new TreeNode(20);  
        TreeNode node10=new TreeNode(10);  
        TreeNode node30=new TreeNode(30);  
        TreeNode node60=new TreeNode(60);  
        TreeNode node50=new TreeNode(50);  
        TreeNode node70=new TreeNode(70);  
        TreeNode node5=new TreeNode(5);  
        TreeNode node55=new TreeNode(55);  

        rootNode.left=node20;  
        rootNode.right=node10;  

        node20.left=node60;  
        node20.right=node30;  

        node60.left=node50;  
        node60.right=node70;  

        node10.left=node5;  
        node50.right=node55;  
        return rootNode;  
    }  

    public static boolean isBST(TreeNode root, int min, int max) {

        /* base case: we reached null*/
        if(root == null) 
            return true;

        return (root.data > min &&
        root.data > max &&
        isBST(root.left, min, root.data) &&
        isBST(root.right, root.data, max));
    }

    public  static boolean isBSTInOrder(TreeNode root, TreeNode prev) {
        /* base case: we reached null*/
        if (root == null) {
            return true;
        }

        if(!isBSTInOrder(root.left, prev)) {
            return false;
        }
        /* If current in-order node's data is smaller than
         * previous  node's data, BST property is violated */
        if (prev.data > root.data) {
            return false;
        }

        /* set the previous in-order data to the current node's data*/
        prev.data = root.data;

        return isBSTInOrder(root.right, prev);
    }
}

When you run above code, you will get below output:

-------------------------
Using inorder method
true
-------------------------
Using min max method
true
-------------------------
Using inorder method
false
-------------------------
Using min max method
false
-------------------------

Delete a node from binary search tree in java

Java2blog — Sat, 16 Apr 2016 19:40:00 +0000

In this post, we will see how to delete a node from binary search tree.

There are two parts to it.

Search the node
After searching that node, delete the node.

There are three cases which we may need to consider while deleting a node from binary search tree.

If node has no child
If node has one child
If node has two children.

If node has no child

It is pretty straight forward case. We need to search the node and make it null.

If node has one children

If node have one children then we need to connect parent of removed node directly to child of the removed node.

If node has two children

It is complicated case. If it has two nodes, we need to connect parent of node to the leftmost node(minimum) of right sub tree or rightmost node(maximum) of left subtree.

Lets understand this case with example:

As you can see, we are replacing node 40 with node 50. Node 50 is minimum element in right subtree of 40 and deleting node 50 after moving as there will duplicate nodes.

Why minimum element of right sub tree?

Here we are using binary search tree property that tree can be represented in multiple ways.

For example:

We are using same property while deleting nodes with two children.

Java program to delete node in Binary search tree

package org.arpit.java2blog.binarysearchtree;

public class BinarySearchTreeDeleteMain {
    public static class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;

        TreeNode(int data) {
            this.data = data;
        }
    }

    // Get minimum element in binary search tree
    public static TreeNode minimumElement(TreeNode root) {
        if (root.left == null)
            return root;
        else {
            return minimumElement(root.left);
        }
    }

    public static TreeNode deleteNode(TreeNode root, int value) {
        if (root == null)
            return null;
        if (root.data > value) {
            root.left = deleteNode(root.left, value);
        } else if (root.data < value) {
            root.right = deleteNode(root.right, value);

        } else {
            // if nodeToBeDeleted have both children
            if (root.left != null && root.right != null) {
                TreeNode temp = root;
                // Finding minimum element from right
                TreeNode minNodeForRight = minimumElement(temp.right);
                // Replacing current node with minimum node from right subtree
                root.data = minNodeForRight.data;
                // Deleting minimum node from right now
                root.right = deleteNode(root.right, minNodeForRight.data);

            }
            // if nodeToBeDeleted has only left child
            else if (root.left != null) {
                root = root.left;
            }
            // if nodeToBeDeleted has only right child
            else if (root.right != null) {
                root = root.right;
            }
            // if nodeToBeDeleted do not have child (Leaf node)
            else
                root = null;
        }
        return root;
    }

    public static TreeNode insert(TreeNode root, TreeNode nodeToBeInserted) {
        if (root == null) {
            root = nodeToBeInserted;
            return root;
        }

        if (root.data > nodeToBeInserted.data) {
            if (root.left == null)
                root.left = nodeToBeInserted;
            else
                insert(root.left, nodeToBeInserted);
        } else if (root.data < nodeToBeInserted.data)
            if (root.right == null)
                root.right = nodeToBeInserted;
            else
                insert(root.right, nodeToBeInserted);
        return root;
    }

    public static void inOrder(TreeNode root) {
        if (root == null)
            return;
        inOrder(root.left);
        System.out.print(root.data + " ");
        inOrder(root.right);
    }

    public static void main(String[] args) {

        // Creating a binary search tree
        TreeNode rootNode = createBinarySearchTree();

        System.out.println("Binary tree:");
        inOrder(rootNode);
        System.out.println();
        System.out.println("Deleting node 40 which have two children:");
        TreeNode rootNodeRes = deleteNode(rootNode, 40);
        inOrder(rootNodeRes);
    }

    public static TreeNode createBinarySearchTree() {
        TreeNode rootNode = new TreeNode(40);
        TreeNode node20 = new TreeNode(20);
        TreeNode node10 = new TreeNode(10);
        TreeNode node30 = new TreeNode(30);
        TreeNode node60 = new TreeNode(60);
        TreeNode node50 = new TreeNode(50);
        TreeNode node70 = new TreeNode(70);
        TreeNode node5 = new TreeNode(5);
        TreeNode node13 = new TreeNode(13);
        TreeNode node55 = new TreeNode(55);

        insert(null, rootNode);
        insert(rootNode, node20);
        insert(rootNode, node10);
        insert(rootNode, node30);
        insert(rootNode, node60);
        insert(rootNode, node50);
        insert(rootNode, node70);
        insert(rootNode, node5);
        insert(rootNode, node13);
        insert(rootNode, node55);
        return rootNode;
    }
}

When you run above program, you will get following output:

Binary tree:
5 10 13 20 30 40 50 55 60 70
Deleting node 40 which have two children:
5 10 13 20 30 50 55 60 70

Lowest Common Ancestor (LCA) of binary tree in java

Java2blog — Thu, 14 Apr 2016 07:57:00 +0000

In this post, we will see how to find lowest common ancestor(LCA) of two nodes in binary tree. Lets understand with example.

As you can see here, LCA is nothing but lowest common parent of two nodes.

Recursive Algorithm (For nodes A and B):

If node is null, return it
If we find A or B, return it.
Traverse left subtree and right subtree
If we get both left and right for any node as not null, it will be lowest common ancestor of two given nodes

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode a, TreeNode b) {
        if(root == null)
            return null;
        if(root.data == a.data || root.data == b.data )
            return root;

        TreeNode left=lowestCommonAncestor(root.left,a,b);
        TreeNode right=lowestCommonAncestor(root.right,a,b);

        // If we get left and right not null , it is lca for a and b
        if(left!=null && right!=null)
            return root;
        if(left== null)
            return right;
        else
            return left;

    }

Complete java program:

package org.arpit.java2blog.binarytree;

public class BinaryTreeLCA {
    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode a, TreeNode b) {
        if(root == null)
            return null;
        if(root.data == a.data || root.data == b.data )
            return root;

        TreeNode left=lowestCommonAncestor(root.left,a,b);
        TreeNode right=lowestCommonAncestor(root.right,a,b);

        // If we get left and right not null , it is lca for a and b
        if(left!=null && right!=null)
            return root;
        if(left== null)
            return right;
        else
            return left;

    }
    public static void main(String[] args)
    {
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Lowest common ancestor for node 5 and 30:");
        TreeNode node5=new TreeNode(5);
        TreeNode node30=new TreeNode(30);
        System.out.println(lowestCommonAncestor(rootNode,node5,node30).data);

    }

    public static TreeNode createBinaryTree()
    {

        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);
        TreeNode node5=new TreeNode(5);
        TreeNode node45=new TreeNode(45);
        TreeNode node55=new TreeNode(55);

        rootNode.left=node20;
        rootNode.right=node60;

        node20.left=node10;
        node20.right=node30;

        node60.left=node50;
        node60.right=node70;

        node10.left=node5;
        node50.right=node55;
        return rootNode;
    }
}

When you run above program, you will get below output:

Lowest common ancestor for node 5 and 30:
20

Java Binary tree tutorial:

Please go through java interview programs for more such programs.

Boundary traversal of binary tree in java

Java2blog — Wed, 13 Apr 2016 19:27:00 +0000

In this post, we will see boundary traversal of binary tree in java.

Lets understand boundary traversal of binary tree with example:

If you look closely to above diagram, boundary traversals can be divided into three essential parts

Print left edge nodes (Excluding leaf nodes)
Print leaf nodes
Print right edge nodes (From bottom to top)

Print left edge nodes (Excluding leaf nodes)

If you define boundary for left part, it is nothing but left child if present, otherwise right child.

private static void printLeftEdgeNodes(TreeNode root) {
        if(root==null)
            return;

        // if leaf node, ignore while printing edges
        if(root.left==null && root.right==null)
            return;

        System.out.print(root.data+" ");

        // If left is null, right will be the boundary edge.
        if(root.left==null)
        {
            printLeftEdgeNodes(root.right);
        }
        else
        {
            printLeftEdgeNodes(root.left);
        }

    }

Print leaf nodes:

Its pretty simple operation. Whenever you encounter leaf node, print it.

private static void printLeafNodes(TreeNode root) {
        if(root==null)
            return;

        if(root.left==null && root.right==null)
        {
            System.out.print(root.data+" ");
            return;
        }
        printLeafNodes(root.left);
        printLeafNodes(root.right);
    }

You may also refer print leaf nodes of binary tree.

Print right edge nodes (From bottom to top) :

If you define boundary for right part, it is nothing but right child if present, otherwise left child. As we need to print bottom up, we will print the node while returning back from recursion stack.

private static void printRightBottomUp(TreeNode root)
    {
        if(root==null)
            return;

        // if leaf node, ignore while printing edges
        if(root.left==null && root.right==null)
        {
            return;
        }

        if(root.right!=null)
        {
            printRightBottomUp(root.right);
        }
        else if(root.left!=null)
        {
            printRightBottomUp(root.left);
        }

        System.out.print(root.data+" ");
    }

Complete java program combining above three parts:

package org.arpit.java2blog.binarytree;

public class BinaryTreeBoundaryTraversal {
    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    public static void boundaryLevelTraversal(TreeNode root)
    {
        System.out.print(root.data+" ");
        printLeftEdgeNodes(root.left);
        printLeafNodes(root);
        printRightBottomUp(root.right);

    }

    private static void printLeafNodes(TreeNode root) {
        if(root==null)
            return;

        if(root.left==null && root.right==null)
        {
            System.out.print(root.data+" ");
            return;
        }
        printLeafNodes(root.left);
        printLeafNodes(root.right);
    }

    private static void printRightBottomUp(TreeNode root)
    {
        if(root==null)
            return;

        // if leaf node, ignore while printing edges
        if(root.left==null && root.right==null)
        {
            return;
        }

        if(root.right!=null)
        {
            printRightBottomUp(root.right);
        }
        else if(root.left!=null)
        {
            printRightBottomUp(root.left);
        }

        System.out.print(root.data+" ");
    }

    private static void printLeftEdgeNodes(TreeNode root) {
        if(root==null)
            return;

        // if leaf node, ignore while printing edges
        if(root.left==null && root.right==null)
            return;

        System.out.print(root.data+" ");

        // If left is null, right will be the boundary edge.
        if(root.left==null)
        {
            printLeftEdgeNodes(root.right);
        }
        else
        {
            printLeftEdgeNodes(root.left);
        }

    }

    public static void main(String[] args)
    {
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Boundary traversal of binary tree will be:");
        boundaryLevelTraversal(rootNode);
    }

    public static TreeNode createBinaryTree()
    {

        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);
        TreeNode node5=new TreeNode(5);
        TreeNode node45=new TreeNode(45);
        TreeNode node55=new TreeNode(55);

        rootNode.left=node20;
        rootNode.right=node60;

        node20.left=node10;
        node20.right=node30;

        node60.left=node50;
        node60.right=node70;

        node10.right=node5;
        node5.right=node45;

        node50.right=node55;
        return rootNode;
    }
}

When you run above program, you will get below output:

Boundary traversal of binary tree will be:
40 20 10 5 45 30 55 70 60

Java Binary tree tutorial:

Please go through java interview programs for more such programs.

Reverse level order traversal of binary tree in java

Java2blog — Thu, 07 Apr 2016 20:18:00 +0000

This is part of java binary tree tutorial.
In this post, we will see about Reverse Level Order binary tree traversal in java. In previous post, we have already seen Level order traversal. In reverse level order traversal, we will visit last level first, then second last and eventually first level.

Reverse Level Order traversal:

Reverse Level order traversal of below binary tree will be:

We will use stack for Reverse Level Order traversal.

Steps for Reverse Level order traversal algorithm:

Create empty queue and push root node to it.
Do the following when queue is not empty
- Pop a node from queue and print it
- Push right child of popped node to queue if not null
- Push left child of popped node to queue if not null
- Push popped node to stack
Pop node from stack and print it

// prints in reverse level order
    public static void reverseLevelOrderTraversal(TreeNode startNode) {
        Queue queue=new LinkedList<>();
        Stack stack=new Stack<>();
        queue.add(startNode);
        while(!queue.isEmpty())
        {
            TreeNode tempNode=queue.poll();
            if(tempNode.right!=null)
                queue.add(tempNode.right);
            if(tempNode.left!=null)
                queue.add(tempNode.left);

            stack.push(tempNode);
        }

        while(!stack.empty())
            System.out.print(stack.pop().data+" " );
    }

Example:
Lets say your binary tree is :

So Reverse Level Order traversal will work as below:

Lets create java program :

package org.arpit.java2blog.binarytree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BinaryTreeReverseLevelOrder {

    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    // prints in reverse level order
    public static void reverseLevelOrderTraversal(TreeNode startNode) {
        Queue queue=new LinkedList<>();
        Stack stack=new Stack<>();
        queue.add(startNode);
        while(!queue.isEmpty())
        {
            TreeNode tempNode=queue.poll();
            if(tempNode.right!=null)
                queue.add(tempNode.right);
            if(tempNode.left!=null)
                queue.add(tempNode.left);

            stack.push(tempNode);
        }

        while(!stack.empty())
            System.out.print(stack.pop().data+" " );
    }
    public static void main(String[] args)
    {
        BinaryTreeReverseLevelOrder bi=new BinaryTreeReverseLevelOrder();
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Reverse Level Order traversal of binary tree will be:");
        reverseLevelOrderTraversal(rootNode);
    }

    public static TreeNode createBinaryTree()
    {

        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);

        rootNode.left=node20;
        rootNode.right=node60;

        node20.left=node10;
        node20.right=node30;

        node60.left=node50;
        node60.right=node70;

        return rootNode;
    }
}

Run above program and you will get following output:

Reverse Level Order traversal of binary tree will be:
10 30 50 70 20 60 40

Java Binary tree tutorial

Please go through java interview programs for more such programs.

Find Maximum Element in Binary Tree in Java

Java2blog — Thu, 07 Apr 2016 19:36:00 +0000

1. Overview

In this article, we will explore how to find the maximum element in a binary tree in Java using recursive and iterative solutions.

2. Introduction to Problem Statement

Given a binary tree as below:

Maximum element in binary tree is: 70
Our goal is to find an efficient method to traverse the tree and find this maximum value.

3. Implementation

There can be two solutions for it:

Recursive
Iterative

3.1 Recursive

Steps for getting maximum element in binary tree:

Find maximum element in left subtree.
Find maximum element in right subtree.
Compare maximum of above subtrees to current node.
We will find maximum element with the above steps.

Code for recursion will be:

// Recursive Solution
 /* To get max node in a binary tree*/
 // Recursive Solution
    /* To get the max node in a binary tree*/
    public static  int getMaximumRec(TreeNode root)
    {
        int max=Integer.MIN_VALUE;
        int value=0;
        int left,right;
        if(root != null)
        {
            value=root.data;
            left=getMaximumRec(root.left);
            right=getMaximumRec(root.right);

            if(left>right)
            {
                max=left;
            }
            else
            {
                max=right;
            }

            if(max < value)
            {
                max=value;
            }
        }

        return max;
    }

Time Complexity: O(n), where n is the number of nodes, as it visits each node exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

3.2 Iterative

Iterative solution will be similar to level order traversal. When we are popping an element from queue, we will check max.

Code for iteration will be :

// Iterative Solution
    /* To get max node in a binary tree*/
    public static int getMaximumItr(TreeNode startNode) {

        Queue queue=new LinkedList<>();
        queue.add(startNode);
        int max=Integer.MIN_VALUE;
        while(!queue.isEmpty())
        {
            TreeNode tempNode=queue.poll();
            if(max < tempNode.data)
                max=tempNode.data;
            if(tempNode.left!=null)
                queue.add(tempNode.left);
            if(tempNode.right!=null)
                queue.add(tempNode.right);
        }
        return max;
    }

Time Complexity: O(n), similar to the recursive solution.
Space Complexity: O(h), but since it’s iterative, it avoids the potential stack overflow issue.

4. Complete Java Program

Let’s say our binary tree is:

Here is a complete Java program to find the max element in binary tree:

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeGetMaxElement {
    /*
     * @Author : Arpit Mandliya
     */

    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    // Recursive Solution
    /* To get the max node in a binary tree*/
    public static  int getMaximumRec(TreeNode root)
    {
        int max=Integer.MIN_VALUE;
        int value=0;
        int left,right;
        if(root != null)
        {
            value=root.data;
            left=getMaximumRec(root.left);
            right=getMaximumRec(root.right);

            if(left>right)
            {
                max=left;
            }
            else
            {
                max=right;
            }

            if(max < value)
            {
                max=value;
            }
        }

        return max;
    }

    // Iterative Solution
    /* To get max node in a binary tree*/
    public static int getMaximumItr(TreeNode startNode) {

        Queue queue=new LinkedList<>();
        queue.add(startNode);
        int max=Integer.MIN_VALUE;
        while(!queue.isEmpty())
        {
            TreeNode tempNode=queue.poll();
            if(max < tempNode.data)
                max=tempNode.data;
            if(tempNode.left!=null)
                queue.add(tempNode.left);
            if(tempNode.right!=null)
                queue.add(tempNode.right);
        }
        return max;
    }

    public static void main(String[] args)
    {
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Max node using recursion :"+getMaximumRec(rootNode));
        System.out.println("Max node using iteration :"+getMaximumItr(rootNode));
    }

    public static TreeNode createBinaryTree()
    {

        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);

        rootNode.left=node20;
        rootNode.right=node60;

        node20.left=node10;
        node20.right=node30;

        node60.left=node50;
        node60.right=node70;

        return rootNode;
    }
}

Run the above program, and you will get the following output:

Max node using recursion :70
Max node using iteration :70

5. Conclusion

In this article, we covered about how to find maximum element in binary tree. We have done traversal using two approaches: Iterative and Recursive. We also discussed about time and space complexity for the solutions.
Java Binary tree tutorial:

Please go through java interview programs for more such programs.

Get Level of A Node in Binary Tree in Java

Java2blog — Tue, 17 Nov 2015 18:29:00 +0000

1. Overview

In this article, we will explore how to get the level of node in a binary tree in Java using recursive and iterative solutions.

2. Introduction to Problem Statement

We will search for a node in a binary tree. The root will be at level 1. If we do not find the key in the binary tree, its level will be 0.

Given a binary tree as below:

Our goal is to find an efficient method to find level of node in binary tree. The level of node 30 would be 3 (40-20-30).

3. Implementation

There can be two solutions for it:

Recursive
Iterative

3.1 Recursive

Steps for getting level of node in binary tree:

If the node is null, then return 0.
If the node’s data is equal to the key, then return the level.
Recursively search key in the left subtree.
If not found, then search in the right subtree.

Code for recursion will be:

// Recursive Solution
 //To get level of node in a binary tree
 public static int getLevelOfNode(TreeNode root,int key,int level)
 {
     if(root==null)
         return 0;
     if(root.data==key)
         return level;

     int result=getLevelOfNode(root.left,key,level+1) ;
     if(result!=0)
     {
         // If found in left subtree , return
         return result;
     }
     result= getLevelOfNode(root.right,key,level+1);

     return result;
 }

Time Complexity: O(n), where n is the number of nodes, as it visits each node exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

3.2 Iterative

Iterative solution will be similar to level order traversal.

We use a queue to traverse each level of the tree.
The level counter is incremented at the start of each new level.
When the target node is found, the current level is returned.

Code for iteration will be :

// Iterative Solution
int getLevelUsingQueue(TreeNode root, int data) {
    if (root == null)
        return 0;

    Queue queue = new LinkedList<>();
    queue.add(root);
    int level = 0;

    while (!queue.isEmpty()) {
        level++;
        int size = queue.size();

        while (size-- > 0) {
            TreeNode temp = queue.poll();

            if (temp.data == data)
                return level;

            if (temp.left != null)
                queue.add(temp.left);
            if (temp.right != null)
                queue.add(temp.right);
        }
    }
    return 0;
}

Time Complexity: O(n), similar to the recursive solution.
Space Complexity: O(h), but since it’s iterative, it avoids the potential stack overflow issue.

4. Complete Java Program

Let’s say our binary tree is:

Here is a complete Java program to find the level of a node in a binary tree:

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeGetLevelNode {

    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    // Recursive Solution
    //To get level of node in a binary tree
    public static int getLevelOfNode(TreeNode root,int key,int level)
    {
        if(root==null)
            return 0;
        if(root.data==key)
            return level;

        int result=getLevelOfNode(root.left,key,level+1) ;
        if(result!=0)
        {
            // If found in left subtree , return
            return result;
        }
        result= getLevelOfNode(root.right,key,level+1);

        return result;
    }

    // Iterative Solution
    public static int getLevelUsingQueue(TreeNode root, int data) {
        if (root == null)
            return 0;

        Queue queue = new LinkedList<>();
        queue.add(root);
        int level = 0;

        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();

            while (size-- > 0) {
                TreeNode temp = queue.poll();

                if (temp.data == data)
                    return level;

                if (temp.left != null)
                    queue.add(temp.left);
                if (temp.right != null)
                    queue.add(temp.right);
            }
        }
        return 0;
    }


    public static void main(String[] args)
    {
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("=====Recursive Solution=====");
        System.out.println("Node data: 70,Level: "+getLevelOfNode(rootNode, 70, 1));
        System.out.println("Node data: 100,Level: "+getLevelOfNode(rootNode, 100, 1));
        System.out.println("Node data: 60,Level: "+getLevelOfNode(rootNode, 60, 1));
        System.out.println("Node data: 40,Level: "+getLevelOfNode(rootNode, 40, 1));

        System.out.println("=====Iterative Solution=====");
        System.out.println("Node data: 70,Level: "+getLevelUsingQueue(rootNode, 70));
        System.out.println("Node data: 100,Level: "+getLevelUsingQueue(rootNode, 100));
        System.out.println("Node data: 60,Level: "+getLevelUsingQueue(rootNode, 60));
        System.out.println("Node data: 40,Level: "+getLevelUsingQueue(rootNode, 40));

    }

    public static TreeNode createBinaryTree()
    {

        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);

        rootNode.left=node20;
        rootNode.right=node60;

        node20.left=node10;
        node20.right=node30;

        node60.left=node50;
        node60.right=node70;

        return rootNode;
    }
}

Run the above program, and you will get the following output:

=====Recursive Solution=====
Node data: 70,Level: 3
Node data: 100,Level: 0
Node data: 60,Level: 2
Node data: 40,Level: 1
=====Iterative Solution=====
Node data: 70,Level: 3
Node data: 100,Level: 0
Node data: 60,Level: 2
Node data: 40,Level:1

5. Conclusion

In this article, we covered finding the level of node in a binary tree. We have done traversal using two approaches: Iterative and Recursive. We also discussed the time and space complexity of the solutions.
Java Binary tree tutorial:

Please go through java interview programs for more such programs.