DS Algo for novice
Published in

DS Algo for novice

Tree || Level Order || populate next node, perfect binary tree

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.

Java Simple Solution w/ Images & Explanation | BFS + DFS + O(1) Optimized BFS

✔️ Solution — I (BFS — Right to Left)

It’s important to see that the given tree is a perfect binary tree. This means that each node will always have both children and only the last level of nodes will have no children.

Now, we need to populate the next pointers of each node with nodes that occur to its immediate right on the same level. This can easily be done with BFS. Since for each node, we require the right node on the same level, we will perform a right-to-left BFS instead of the standard left-to-right BFS.

Before starting the traversal of each level, we would initialize a rightNode variable set to NULL. Then, since we are performing right-to-left BFS, we would be starting at the rightmost node of each level. We set the next node of cur as rightNode and update rightNode = cur. This would ensure that each node would be assigned rightNode properly while traversing from right to left.
Also, if cur has a child, we would first push its right child and only then its left child (since we are doing right-to-left BFS). Once BFS is completed (after queue becomes empty), all next nodes would be populated and we can finally return root.

class Solution {
public Node connect(Node root) {
if(root == null) return null;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
Node rightNode = null;
for(int i = q.size(); i > 0; i--) {
Node cur = q.poll();
cur.next = rightNode;
rightNode = cur;
if(cur.right != null) {
q.offer(cur.right);
q.offer(cur.left);
}
}
}
return root;
}
}

Time Complexity : O(N), where N is the number of nodes in the given tree. We only traverse the tree once using BFS which requires O(N).
Space Complexity : O(W) = O(N), where W is the width of the given tree. This is required to store the nodes in the queue. Since the given tree is a perfect binary tree, its width is given as W = (N+1)/2 ≈ O(N)

✔️ Solution — II (DFS)

We can also populate the next pointers recursively using DFS. [Tree is a perfect binary tree]

In the above solution, we had access to right nodes since we traversed in level-order. But in DFS, once we go to the next level, we cant get access to right node. So, we must update next pointers of the child of each node from its parent’s level itself. Thus at each recursive call -

  • If child node exists:
  • assign next of left child node as right child node: root -> left -> next = root -> right. Note that, if one child exists, the other exists as well.
  • assign next of right child node as the left child of root’s next (if root’s next exists): root -> right -> next = root -> next -> left.
    How? We need the right immediate node of the right child. This won't exist if the current root's next node doesn't exist. If the next node of the current root is present (the next pointer of the root would already be populated in above level), the right immediate node of root's right child must be root's next's left child because if the child of root exists, then the child of root's next must also exist.
  • If a child node doesn’t exist, we have reached the last level, we can directly return since there are no child nodes to populate their next pointers
class Solution {
public Node connect(Node root) {
if(root == null) return null;
Node L = root.left, R = root.right, N = root.next;
if(L != null) {
L.next = R;
if(N != null) R.next = N.left;
connect(L);
connect(R);
}
return root;
}
}

Time Complexity : O(N), each node is only traversed once
Space Complexity : O(logN), required for a recursive stack. The maximum depth of recursion is equal to the height of tree which in this case of perfect binary tree is equal to O(logN)

✔️ Solution — III (BFS — Space-Optimized Appraoch)

This is a combination of the above logics- we will traverse in a BFS manner but populate the next pointers of the bottom level just as we did in the DFS solution.

Usually, standard DFS/BFS takes O(N) space, but since we are given the next pointers in each node, we can use them to space-optimized our traversal to O(1).

  • We first populate the next pointers of child nodes of the current level. This makes it possible to traverse the next level without using a queue. To populate next pointers of child, the exact same logic as above is used
  • We simply traverse to root’s left child and repeat the process — traverse current level, fill next pointers of child nodes and then again update root = root -> left. So, we are basically performing standard BFS traversal in O(1) space by using next pointers to our advantage
  • The process continues till we reach the last level of the tree
class Solution {
public Node connect(Node root) {
Node head = root;
for(; root != null; root = root.left)
for(Node cur = root; cur != null; cur = cur.next)
if(cur.left != null) {
cur.left.next = cur.right;
if(cur.next != null) cur.right.next = cur.next.left;
} else break;

return head;
}
}

Time Complexity : O(N), we only traverse each node once, basically doing a standard BFS.
Space Complexity : O(1), only constant extra space is being used.

Thanks to Abhishek, for a great walkthrough.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store