Objective: – Given a binary tree with three pointers left, right and nextSibling). Write the program to provide the nextsibling pointers.
This problem can also be referred as “Populating Next Right Pointers in Each Node”
Example:
Approach:
- Use Recursion.
- Start from the root, if root’s left node is not null then make it point to the root’s right child.
- check if root’s nextsibling is not null, if NOT then make the next sibling of root’s right node point to the root’s nextsibling’s left child. (In our example node 5 points node 6, as per our statement, Parent of node 5 is Node 2, next sibling of node 2 is node 3, and left child of node 2 is node 6, So Node 5 will points to Node 6 )
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class PutNextSiblingLinks { | |
| public Node provideSiblings(Node root) { | |
| if (root != null) { | |
| if (root.left != null) { // check if left node is not null | |
| // make the left node's sibling points to the right node of root | |
| root.left.nextSibling = root.right; | |
| } | |
| if (root.right != null) { | |
| if (root.nextSibling != null)// check if root has any sibling | |
| // make the right node's sibling points root's next siblings | |
| // left node | |
| root.right.nextSibling = root.nextSibling.left; | |
| } | |
| provideSiblings(root.left); | |
| provideSiblings(root.right); | |
| return root; | |
| } | |
| return null; | |
| } | |
| public void printLevel(Node n) { | |
| while (n != null) { | |
| System.out.print(" " + n.data); | |
| n = n.nextSibling; | |
| } | |
| } | |
| public static void main(String[] args) { | |
| Node root = new Node(1); | |
| root.left = new Node(2); | |
| root.right = new Node(3); | |
| root.left.left = new Node(4); | |
| root.left.right = new Node(5); | |
| root.right.left = new Node(6); | |
| root.right.right = new Node(7); | |
| PutNextSiblingLinks i = new PutNextSiblingLinks(); | |
| Node x = i.provideSiblings(root); | |
| i.printLevel(x); | |
| System.out.println(""); | |
| i.printLevel(x.left); | |
| System.out.println(""); | |
| i.printLevel(x.left.left); | |
| } | |
| } | |
| class Node { | |
| int data; | |
| Node left; | |
| Node right; | |
| Node nextSibling; | |
| public Node(int data) { | |
| this.data = data; | |
| } | |
| } |
Output:
1 2 3 4 5 6 7
This code will fail, when node has only left or right child in each level.