Tree data structure traversal

There are 2 types of traversal we can do in tree

1. BFS
2. DFS

In BFS we are traversing a tree in level order, where we traverse the trees each level

public static void LevelOrderTraversal(Node root) throws Exception
{
    if (root == null)
    {
        return;
    }
    Queue<Node> q= new Queue<>();
    q.enqueue(root);
    q.enqueue(null);
    while(!q.isEmpty())
    {
        Node node = q.dequeue();
        if(node == null)
        {
            q.enqueue(null);
            continue;
        }
        System.out.println("Val"+ node.val);
        if (node.left != null) q.enqueue(node.left);
        if (node.right != null) q.enqueue(node.right);
    }
}

where we use the Queue from java import sun.misc.Queue; and Node as below

class Node{
    public int val;
    public Node left;
    public Node right;
    Node(int a)
    {
        val= a;
        left=null;
        right= null;
    }
}

Similarly, we have DFS where each node traverse after its child node traversed successfully. there are 3 ways to traverse child nodes

1. Pre-order (root, left, right)

public static void PreOrderTraversal( Node root)
{
    if( root == null)
    {
        return;
    }
    System.out.println("Val:"+root.val);
    PreOrderTraversal(root.left);
    PreOrderTraversal(root.right);
}

2. In-order (left, root, right)

public static void InOrderTraversal( Node root)
{
    if( root == null)
    {
        return;
    }
    InOrderTraversal(root.left);
    System.out.println("Val:"+root.val);
    InOrderTraversal(root.right);
}

3. Post-order (left, right, root)

public static void PostOrderTraversal( Node root)
{
    if( root == null)
    {
        return;
    }
    PostOrderTraversal(root.left);
    PostOrderTraversal(root.right);
    System.out.println("Val:"+root.val);
}

all the above 3 methods use the system stack to store the next node information to traverse. we can also use a stack explicitly and traverse the tree all three ways.

How can we keep track of the parent node in a binary tree while traversing on DFS?

There are 2 ways to solve this approach.

1. Keep track of the parent node in each child node.
2. while traversing the tree in DFS keep track of the parent node

The first approach is easy but it will take additional space for the parent node. The second approach to keep track of parent nodes while calling in recursion. It can be used in the below set of questions.

1. Find LCA (least common ancestor) of 2 nodes

2. Find a path from the node to root

3. Sum of root to the node

4. Find k distance nodes from a given node.

public static Node TrackParentOfNode(Node root, int level, Node target)
{
    // Base case
    if (root == null)
    {
        return null;
    }

    // Return when we found the node
    if(root.val == target.val)
    {
        return root;
    }

    Node left =  TrackParentOfNode(root.left, level+1, target);
    Node right = TrackParentOfNode(root.right, level+1, target);
    
    if(left != null || right != null)
    {
        System.out.println("Level:"+level+", Parent:"+ root.val);
    }

    return left == null ? right: left;
}

if we want to get which side of the parent the child node exists and what is the other side of the parent node.

public static Node TrackParentOfNode(Node root, int level, Node target)
{
    // Base case
    if (root == null)
    {
        return null;
    }
    /* //In Case if LCA we can return if either one is matching
    if(root.val == target1.val || root.val == target2.val)
    {
        return root;
    }*/
    System.out.println("Val: "+ root.val);
    // Return when we found the node
    if(root.val == target.val)
    {
        return root;
    }

    Node left =  TrackParentOfNode(root.left, level+1, target);
    Node right = TrackParentOfNode(root.right, level+1, target);
    // If the node is in the left side then just get
    if(left != null)
    {
        System.out.println("Level:"+level+", Parent:"+ root.val + " & Parent's right:"+ root.right.val);
    }

    if(right != null)
    {
        System.out.println("Level:"+level+", Parent:"+ root.val + " & Parent's left:"+ root.left.val);
    }

    // if we are searching for 2 nodes and their common node (LCA) then check if both left and right are not null.
    /*if (left != null && right!= null)
    {
        System.out.println("LCA:"+root.val);
    }*/

    return left == null ? right: left;
}

How can we track all the non-leaf nodes with their level?

public static Node TrackParentNodesWithLevel(Node root, int level)
{
    // Base case
    if (root == null)
    {
        return null;
    }

    // Return when we found the node
    if(root.left == null && root.right == null)
    {
        return root;
    }

    Node left =  TrackParentNodesWithLevel(root.left, level+1);
    Node right = TrackParentNodesWithLevel(root.right, level+1);

    if(left != null || right != null)
    {
        System.out.println("Level:"+level+", Parent:"+ root.val);
    }

    return left == null ? right: left;
}

output

Level:3, Parent:7
Level:2, Parent:4
Level:1, Parent:2
Level:3, Parent:12
Level:2, Parent:11
Level:1, Parent:3
Level:0, Parent:1

Find K Distance Nodes from a given node

public static void FindKDistanceChildNodes(Node root, int k)
{
    if(root == null || k<0) {
        return;
    }
    if (k == 0) {
        System.out.println("val" + root.val);
    }
    FindKDistanceChildNodes(root.left, k-1);
    FindKDistanceChildNodes(root.right, k-1);
}

public static Node FindKDistanceNodeFromAGivenNode(Node root, Node target, int k,int a[])
{
    // Base case
    if (root == null)
    {
        return null;
    }

    // Return when we found the node
    if(root.val == target.val)
    {
        System.out.println("Start printing child nodes");
        FindKDistanceChildNodes(root, k);
        return root;
    }
    Node left =  FindKDistanceNodeFromAGivenNode(root.left,target, k,a);
    Node right = FindKDistanceNodeFromAGivenNode(root.right, target, k,a);

    if(left != null){
        // this is used as an array because in recursive call also we can pass this as ref and increment the value.
        a[0]++;
        //System.out.println("Parent:"+ root.val + " & Parent's right:"+ root.right.val+ ", k="+k+", a="+a[0]);
        // Check the k'th distance of the parent, if it is greater than 0 go to right side
        if(k-a[0] > 0) {
            // while moving to right decrease the k by 1
            FindKDistanceChildNodes(root.right, k-a[0]-1);
        }
        else if(k-a[0] == 0)
        {
            // if parent is in k distance  then just print root(parent)
            FindKDistanceChildNodes(root, k-a[0]);
        }
    }
    if(right != null)
    {
        a[0]++;
        System.out.println("Parent:"+ root.val + " & Parent's left:"+ root.left.val+ ", k="+k+", a="+a[0]);
        if(k-a[0] > 0) {
            // while moving to right decrease the k by 1
            FindKDistanceChildNodes(root.left, k-a[0]-1);
        }
        else if(k-a[0] == 0)
        {
            // if parent is in k distance  then just print root(parent)
            FindKDistanceChildNodes(root, k-a[0]);
        }
    }
    return left == null ? right: left;
}

Minified version of FindKDistanceNodeFromAGivenNode function is as below.

public static Node FindKDistanceNodeFromAGivenNode(Node root, Node target, int k,int a[])
{
    if (root == null){
        return null;
    }
    if(root.val == target.val){
        FindKDistanceChildNodes(root, k);
        return root;
    }
    Node left =  FindKDistanceNodeFromAGivenNode(root.left,target, k,a);
    Node right = FindKDistanceNodeFromAGivenNode(root.right, target, k,a);
    if(left != null || right != null) {
        a[0]++;
        if(k-a[0] >= 0) {
            FindKDistanceChildNodes(
                    (k-a[0] == 0) ? root : (left != null) ? root.right : root.left,
                    (k-a[0] == 0) ? 0 : k-a[0]-1);
        }
    }
    return left == null ? right: left;
}

call this Function using FindKDistanceNodeFromAGivenNode (a, new Node(2), 3, new int[1]); for below tree

output:

val8
val9
val10
val11