educative.io

How to complete with O(1) space?

Courses
, ,
#1

I got this problem in an interview and was told it should be possible with O(1) space. Any ideas how?

#2

I managed to work out a solution that uses O(1) space (implementation is in Ruby):

def connect_level_order_siblings(root)
  current_node, next_level = root, nil
  while current_node
    next_level = current_node.left || current_node.right unless next_level

    next_right = get_next_right(current_node)
    current_node.left.next_right = current_node.right ? current_node.right : next_right if current_node.left
    current_node.right.next_right = next_right if current_node.right

    if current_node.next_right
      current_node = current_node.next_right
    else
      current_node, next_level = next_level, nil
    end
  end
end

def get_next_right(node)
  next_right = nil
  until next_right || node.next_right.nil?
    node = node.next_right
    next_right = node.left || node.right
  end
  next_right
end
#3

Here is the Java code using constant space.

import java.util.*;

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode next;

  TreeNode(int x) {
    val = x;
    left = right = next = null;
  }

  // level order traversal using 'next' pointer
  public void printLevelOrder() {
    TreeNode nextLevelRoot = this;
    while (nextLevelRoot != null) {
      TreeNode current = nextLevelRoot;
      nextLevelRoot = null;
      while (current != null) {
        System.out.print(current.val + " ");
        if (nextLevelRoot == null) {
          if (current.left != null)
            nextLevelRoot = current.left;
          else if (current.right != null)
            nextLevelRoot = current.right;
        }
        current = current.next;
      }
      System.out.println();
    }
  }
};

class ConnectLevelOrderSiblings {
 
  public static void connect(TreeNode root) {
    if (root == null)
      return;

    TreeNode current = root;
    TreeNode prev = root;
    TreeNode currentLevelLast = root;

    TreeNode nextLevelFirst = null;
    TreeNode nextLevelLast = null;

    while(current != null) {
      if(current.left != null) {
        if(prev != null)
          prev.next = current.left;
        prev = nextLevelLast = current.left;
        if(nextLevelFirst == null)
          nextLevelFirst = current.left;
      }

      if(current.right != null){
        if(prev != null)
          prev.next = current.right;
        prev = nextLevelLast = current.right;
        if(nextLevelFirst == null)
          nextLevelFirst = current.right;
      }
    
      if(current == currentLevelLast) { // reached at the end of the current level
        current.next = null;
        // set references for the next level
        current = nextLevelFirst;
        currentLevelLast = nextLevelLast;
        prev = nextLevelFirst = null;
      } else {
        current = current.next;  
      }
    }
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(12);
    root.left = new TreeNode(7);
    root.right = new TreeNode(1);
    root.left.left = new TreeNode(9);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);
    ConnectLevelOrderSiblings.connect(root);
    System.out.println("Level order traversal using 'next' pointer: ");
    root.printLevelOrder();
  }
}
1 Like
#4

Here us Python solution O(1) space:

  def connect_level_order_siblings(root):

  cur,nxt = root, root.left if root else None
        
  while cur and nxt:
      cur.left.next = cur.right 
      if cur.next and cur.right and cur.next.left:
        cur.right.next = cur.next.left
            
      cur = cur.next
      if not cur:
          cur = nxt
          nxt = cur.left
  return root