Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Connect Level Order Siblings

Problem Statement

Given a root of the binary tree, connect each node with its level order successor. The last node of each level should point to a null node.

Examples

Example 1:

  • Input: root = [1, 2, 3, 4, 5, 6, 7]
  • Output: 
    [1 -> null]
[2 -> 3 -> null]
[4 -> 5 -> 6 -> 7 -> null]
  • Explanation:
    The tree is traversed level by level using BFS. Each node is connected to its next right node at the same level. The last node of each level points to null.

Example 2:

  • Input: root = [12, 7, 1, 9, null, 10, 5]
  • **Output:

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Avinash Agarwal

· 4 years ago

public TreeNode connect(TreeNode root) {

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

// Start with the root node. There are no next pointers // that need to be set up on the first level Node leftmost = root;

// Once we reach the final level, we are done while (leftmost.left != null) {

// Iterate the "linked list" starting from the head // node and using the next pointers, establish the // corresponding links for the next level Node head = leftmost;

while (head != null) {

// CONNECTION 1 head.left.next = head.right;

// CONNECTION 2 if (head.next != null) { head.right.next = head.next.left; }

// Progress along the list (nodes on the current level) head = head.next; }

// Move onto the next level leftmost = leftmost.left; }

return root; }

This is a solution with O(1) space.

Show 2 replies