- Given a binary tree, we want to connect the nodes or siblings at same level using recursive algorithm.
- Perform preOrder traversal of a binary tree using depth first search recursive algorithm.
- The node at every level will hold a reference of its immediate next (or right) sibling (if exists).
- In a binary tree, we generally have following information.
- Data node
- Left Child
- Right Child
To have next sibling reference, we will add another field to a binary tree i.e. nextSibling, which will connects the sibling nodes at same level. With addition of next reference, binary tree will looks like as shown in the Fig 1.
Example – connect nodes at same level
- Nodes at same level are connected (Refer Fig 2).
- Level 0:
- Node A (root node) does not have right sibling node.
- A.next set to null.
- At level 1
- Node B.next set to next sibling Node C
- B.next = C.
- Node C does not have any right sibling.
- C.next = null.
- Node B.next set to next sibling Node C
- Similarly, Nodes at Level 2 are connected.
Algorithm – set next reference (or next Sibling) of nodes at same level
- Node A does not have any sibling.
- Node A nextSibling will be set to null.
- Setting nextSibling reference for Node A’ left (B) & right child (C)
- A’s left child i.e. B next reference set to A’s right child
- Node B will start pointing to Node C
- A.left.nextSibling = A.right [Node B]
- Node B will start pointing to Node C
- A’s right child i.e. Node C
- Node A does not have any siblings
- So Node A’s right child C will not have any sibling
- Simply set the Node C right child to null
- A.right.nextSibling = null [Node C]
- Node A does not have any siblings
- A’s left child i.e. B next reference set to A’s right child
- Setting the next reference for Node B’s left (Node D) and right child (Node E)
- B’ left child i.e. D next reference set to B’s right child
- Node D will start pointing to Node E
- B.left.nextSibling = B.right [Node D]
- Node D will start pointing to Node E
- B’s right child i.e. Node E
- As Node B have sibling [Set in step 2]
- Setting the Node E next child as follow
- Set the next of B.right [Node E] to left of B.next [Node C]
- Node E will start pointing to Node F
- B.right.nextSibling = B.nextSibling.left
- B’ left child i.e. D next reference set to B’s right child
- Similarly set the next reference for rest of nodes in a binary tree.
Algorithm conclusion
- Left child of current node set to right child of current node [Condition 1]
- Right child of current node will have two condition [Condition 2 and Condition 3]
- Current node having next sibling [Example: Node B & Node C are siblings]
- Current Node does not have any next sibling [Example: Node A does not having any sibling]
Program – Connect the siblings of binary tree using DFS algorithm.
1.) NextSiblingPointer Class:
- Perform pre order traversal of binary tree.
- Setting the nextSibling reference of nodes as per above algorithm.
package org.learn.Question; import org.learn.PrepareTree.Node; public class NextSiblingPointer { public static void nextSiblingPointer(Node node) { if(null == node) { return; } //if we have left child if(node.left != null) { node.left.nextSibling = node.right; } //if we have right child if(node.right != null) { //if current node has sibling, then left set // if(node.nextSibling != null) { node.right.nextSibling = node.nextSibling.left; } else { node.right.nextSibling = null; } } nextSiblingPointer(node.left); nextSiblingPointer(node.right); return; } public static void printUsingNextSibling(Node root) { Node node = null; int level = 0; while( root != null) { node = root; System.out.printf("Level %d data ",level++); while(node != null) { System.out.printf("%d ",node.data); node = node.nextSibling; } System.out.println(""); root = root.left; } } }
2.) Node Class:
The class representing the nodes of binary tree. Node class has following attributes
- Data Node
- left child
- right child
- nextSibling
package org.learn.PrepareTree; public class Node { public int data; public Node left; public Node right; public Node nextSibling; public Node(int num) { this.data = num; this.left = null; this.right = null; this.nextSibling = null; } public Node() { this.left = null; this.right = null; this.nextSibling = null; } public static Node createNode(int number) { return new Node(number); } }
3.) App Class:
- We are creating the binary tree in main function & calling NextSiblingPointer class to connect the sibling nodes in a binary tree.
package org.learn.Client; import org.learn.PrepareTree.Node; import org.learn.Question.NextSiblingPointer; public class App { public static void main( String[] args ) { /* 1 / \ 2 3 / \ / \ 4 5 6 7 */ Node root = Node.createNode(1); root.left = Node.createNode(2); root.right = Node.createNode(3); // left sub tree root.left.left = Node.createNode(4); root.left.right = Node.createNode(5); // right subtree root.right.left = Node.createNode(6); root.right.right = Node.createNode(7); NextSiblingPointer.nextSiblingPointer(root); NextSiblingPointer.printUsingNextSibling(root); } }
Output – connect nodes at same level (set next sibling) in binary tree
Level 0 data 1 Level 1 data 2 3 Level 2 data 4 5 6 7