Vishy tech notes

LeetCode 2020 Dec 6 Populating Next Right Pointers in Each Node

VISWAPRASATH KS's photo
VISWAPRASATH KS
·

4 min read

Problem Statement: We have to assign next value of each node. The next value should be the node which is in the right side of the current node at the same level.

The question is Leetcode

Input will be Single Root Node. Pre-checks whether root is null or not. If null then return null as response.

Pseudo Code

  • The First step is to check whether root node is not null. If it is not null, then we have to move to next step.
  • We first have to find the next value for the root's right.
  • To find the next node, first we have to find the root's next. The top most root node wont have next generally; so its immediate right node's next will be null.
  • In case we have to find the next node for others, the first step is we need to find the root's next node .
  • After we find the root's next; we have to find out whether there is left node first. In case left node exist; then it will be next node; else if right node exist then it will be next node.
  • In case the root's next dont have both left and right; we have to move to current nodes next; and check the above condition.
  • We have to repeat above 3 steps until there is no next.

To find the Next node

    private Node getNodeToAssign(Node root){

        if(root != null){
        Node tempNode = root.next;
            while(tempNode != null){
            if(tempNode.left != null){
                return tempNode.left;
            } else if(tempNode.right!=null){
                return tempNode.right;
            }
            tempNode = tempNode.next;
            }
        }
        return null;

    }
  • Once the right next node is set; we have to iterate for all the right side child nodes recursively.
  • After this we have to find the next node for root's left.
  • Then we have to iterate for all the left side child nodes recursively.
  • Finally return the root node. 
public Node connect(Node root) {

        if(root==null){
            return null;
                }else if(root  != null){

            if(root.right!=null){
                root.right.next=getNodeToAssign(root);
                connect(root.right);
            }
            if(root.left!=null){

                root.left.next=root.right != null ? root.right : getNodeToAssign(root);
                    connect(root.left);

            }
        }

        return root;

        }

Difficulty level for this program is easy. Its just we have to be careful in finding the next node. We have to consider the input size of tree with 15 nodes to capture edge cases also.

data structures