Home/

...

/

Connect Level Order Siblings (medium)

Connect Level Order Siblings (medium)

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Connect Level Order Siblings (medium) lesson:

Press + to interact
Python 3.5
from __future__ import print_function
from collections import deque
class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left, self.right, self.next = None, None, None
  # level order traversal using 'next' pointer
  def print_level_order(self):
    nextLevelRoot = self
    while nextLevelRoot:
      current = nextLevelRoot
      nextLevelRoot = None
      while current:
        print(str(current.val) + " ", end='')
        if not nextLevelRoot:
          if current.left:
            nextLevelRoot = current.left
          elif current.right:
            nextLevelRoot = current.right
        current = current.next
      print()
def connect_level_order_siblings(root):
  # TODO: Write your code here
  return
def main():
  root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
  root.left.left = TreeNode(9)
  root.right.left = TreeNode(10)
  root.right.right = TreeNode(5)
  connect_level_order_siblings(root)
  print("Level order traversal using 'next' pointer: ")
  root.print_level_order()
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

root2 = TreeNode(1)
  root2.left = TreeNode(2)
        root2.left.left = TreeNode(3)
        root2.left.right = TreeNode(3)
  root2.right = TreeNode(2)
        root2.right.left = TreeNode(4)
        root2.right.right = TreeNode(4)

#Visual representation of the tree is as follows

     ___ 1 ___ 
    |         |
  _ 2 _    __ 2 _ 
 |     |  |      |
 3     3  4      4

Iteration No.

Line No.

levelSize

previousNode

currentNode

queue

Tree State

-

32

-

None

-

[1]

_ 1 ____

| |

_ 2 _ _ 2 _

| | | |

3 3 4 4

1

34-35

1

None

-

[1]

remains the same

1

37-40

1

None

1

[]

_ 1 ____

| |

_ 2 _ _ 2 _

| | | |

3 3 4 4

1

41

1

1

1

[]

remains the same

1

44-47

1

1

1

[2,2]

remains the same

2

34-35

2

None

-

[2,2]

remains the same

1

37-40

2

None

2

[2]

_ 1 ____

| |

_ 2 _ _ 2 _

| | | |

3 3 4 4

1

41

2

2

2

[2]

remains the same

1

44-47

2

2

2

[2,3,3]

remains the same

2

37-40

2

2

2

[3,3]

_ 1 ____

| |

_ 2 _ ----> _ 2 _

| | | |

3 3 4 4

2

41

2

2

2

[3,3]

remains the same

2

44-47

2

2

2

[3,3,4,4]

remains the same

3

34-35

4

None

-

[3,3,4,4]

remains the same

1

37-40

4

None

3

[3,4,4]

remains the same



1

41

4

3

3

[3,4,4]

remains the same

1

44-47

4

3

3

[3,4,4]

remains the same

2

37-40

4

3

3

[4,4]

_ 1 ____

| |

_ 2 _ ----> _ 2 _

| | | |

3 ---> 3 4 4

2

41

4

3

3

[4,4]

remains the same

2

44-47

4

3

3

[4,4]

remains the same

3

37-40

4

3

4

[4]

_ 1 ____

| |

_ 2 _ ----> _ 2 _

| | | |

3 ---> 3--> 4 4

3

41

4

4

4

[4]

remains the same

3

44-47

4

4

4

[4]

remains the same

4

37-40

4

4

4

[]

_ 1 ____

| |

_ 2 _ ----> _ 2 _

| | | |

3 ---> 3---> 4 ---> 4

4

41

4

4

4

[]

remains the same

4

44-47

4

4

4

[]

remains the same

Sample Input #2

Students may be encouraged to complete the dry-run with this input:

root = TreeNode(12)
  root.left = TreeNode(7)
       root.left.left = TreeNode(9)
  root.right = TreeNode(1)
       root.right.left = TreeNode(10)
       root.right.right = TreeNode(5)

#Visual representation of the tree is as follows:

      _ 12 _ 
     |      |
   _ 7   __ 1 _ 
  |     |      |
  9     10     5

Iteration No.

Line No.

levelSize

previousNode

currentNode

queue

Tree State

-

32

-

-

-

[12]

_ 12 _

| |

_ 7 __ 1 _

| | |

9 10 5

1

34-35

1

None

-

[12]

remains the same

1

37-40

1

None

12

[]

remains the same

1

41

1

12

12

[]

remains the same

1

44-47

1

12

12

[7,1]

remains the same

2

34-35

2

None

-

[7,1]

remains the same

1

37-40

2

None

7

[1]

remains the same

1

41

2

7

7

[1]

remains the same

1

44-47

2

7

7

[1,9]

remains the same

2

37-40

2

7

1

[9]

_ 12 _____

| |

_ 7 ---> __ 1 _

| | |

9 10 5

2

41

2

1

1

[9]


2

44-47

2

1

1

[9,10,5]


...

...

...

...

...

...


Step-by-step solution construction

Let’s iterate the tree level by level and add all its nodes in the queue. For each level, we traverse all the nodes at that level and add the children of each node to the queue (lines 145-152).

Press + to interact
Python 3.5
from __future__ import print_function
from collections import deque
class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left, self.right, self.next = None, None, None
  def __repr__(self):
    return str(self.val)
  # level order traversal using 'next' pointer
  def print_level_order(self):
    nextLevelRoot = self
    while nextLevelRoot:
      current = nextLevelRoot
      nextLevelRoot = None
      while current:
        print(str(current.val) + " ", end='')
        if not nextLevelRoot:
          if current.left:
            nextLevelRoot = current.left
          elif current.right:
            nextLevelRoot = current.right
        current = current.next
      print()
def height(node):
	if (node == None):
		return 0
	return 1 + max(height(node.left), height(node.right))
def draw_node(output, link_above, node, level, p, link_char):
	if (node == None): 
 		return
	out = "["
	h = len(output)
	SP = " "
	if (p < 0):
		for s in output:
			if (s):
				s = " "*(-1*p) + s
    
		for s in link_above:
			if (s):
				s = " "*(-1*p) + s
	if level < h - 1:
		p = max(p, len(output[level + 1]))
	if (level > 0):
		p = max(p, len(output[level - 1]))
	p = max(p, len(output[level]))
	# Fill in to left
	if (node.left):
		leftData = SP + str(node.left.val) + SP
		draw_node(output, link_above, node.left, level + 1, p - len(leftData),'L')
		p = max(p, len(output[level + 1]))
	# Enter this data
	space = p - len(output[level])
	if (space > 0):
		output[level] += (' ' * space)
	node_data = SP + str(node.val) + SP
	output[level] += node_data
	# Add vertical link above
	space = p + len(SP) - len(link_above[level])
	if (space > 0):
		link_above[level] += (' ' * space)
	link_above[level] += link_char
	# Fill in to right
	if (node.right):
		draw_node(output, link_above, node.right, level + 1, len(output[level]),'R')
  
def display_tree(root):
	if (root == None):
		print("\tNone")
	h = height(root)
	output = []
	link_above = []
	for i in range(0,h): 
				output.append("")
				link_above.append("")
	draw_node(output, link_above, root, 0, 5, ' ')
	# Create link lines
	for i in range(h):
		for j in range(len(link_above[i])):
			if (link_above[i][j] != ' '):
				size = len(output[i - 1])
				if (size < j + 1):
					output[i - 1] += " " *(j + 1 - size)
				jj = j
				if (link_above[i][j] == 'L'):
					while (output[i - 1][jj] == ' '):
						jj += 1
					for k in range(j+1, jj-1):
						str1 = output[i - 1]
						list1 = list(str1)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
				elif(link_above[i][j] == 'R'):
					while (output[i - 1][jj] == ' '):
						jj-=1
					
					# k = j-1
					for k in range(j-1,jj+1,-1):
						temp = output[i - 1]
						list1 = list(temp)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
						k = k - 1
      
				str1 = link_above[i]
				list1 = list(str1)
				list1[j] = '|'
				link_above[i] = ''.join(list1)
					
	# Output
	for i in range(h):
		if (i):
			print("\t" , link_above[i])
		print("\t" , output[i])
def connect_level_order_siblings(root):
  if root is None:
    return
  queue = deque()
  queue.append(root)
  iteration = 0
  while queue:
    previousNode = None
    levelSize = len(queue)
    print("\tIteration: ", iteration+1)
    iteration +=1
    print("\t\tpreviousNode: ",previousNode)
    print("\t\tlevelSize: ",levelSize)
    # connect all nodes of this level
    for _ in range(levelSize):
      currentNode = queue.popleft()
      print("\t\tcurrentNode: ",currentNode)
      # insert the children of current node in the queue
      if currentNode.left:
        queue.append(currentNode.left)
      if currentNode.right:
        queue.append(currentNode.right)
      print("\t\t",queue)
def main():
  #Tree 1
  root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
  root.left.left = TreeNode(9)
  root.right.left = TreeNode(10)
  root.right.right = TreeNode(5)
  #Tree 2
  root2 = TreeNode(1)
  root2.left = TreeNode(2)
  root2.left.left = TreeNode(3)
  root2.left.right = TreeNode(3)
  root2.right = TreeNode(2)
  root2.right.left = TreeNode(4)
  root2.right.right = TreeNode(4)
  trees = [root,root2]
  for tree in trees:
	  print("Input Tree: ")
	  display_tree(tree)
	  connect_level_order_siblings(tree)
	  print("-"*100+"\n")
main()

In the code above, notice the pop operation on line 146. This is the point in the code where need to add the connecting logic.

In the code below (lines 148-151), for each node we pop, we connect it to the previous node by setting the previous node’s next pointer to the current node. To keep track of the previous node, we set the previousNode to the currentNode at the end of each iteration (line 152).

Press + to interact
Python 3.5
from __future__ import print_function
from collections import deque
class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left, self.right, self.next = None, None, None
  def __repr__(self):
    return str(self.val)
  # level order traversal using 'next' pointer
  def print_level_order(self):
    nextLevelRoot = self
    while nextLevelRoot:
      current = nextLevelRoot
      nextLevelRoot = None
      while current:
        print(str(current.val) + " ", end='')
        if not nextLevelRoot:
          if current.left:
            nextLevelRoot = current.left
          elif current.right:
            nextLevelRoot = current.right
        current = current.next
      print()
def height(node):
	if (node == None):
		return 0
	return 1 + max(height(node.left), height(node.right))
def draw_node(output, link_above, node, level, p, link_char):
	if (node == None): 
 		return
	out = "["
	h = len(output)
	SP = " "
	if (p < 0):
		for s in output:
			if (s):
				s = " "*(-1*p) + s
    
		for s in link_above:
			if (s):
				s = " "*(-1*p) + s
	if level < h - 1:
		p = max(p, len(output[level + 1]))
	if (level > 0):
		p = max(p, len(output[level - 1]))
	p = max(p, len(output[level]))
	# Fill in to left
	if (node.left):
		leftData = SP + str(node.left.val) + SP
		draw_node(output, link_above, node.left, level + 1, p - len(leftData),'L')
		p = max(p, len(output[level + 1]))
	# Enter this data
	space = p - len(output[level])
	if (space > 0):
		output[level] += (' ' * space)
	node_data = SP + str(node.val) + SP
	output[level] += node_data
	# Add vertical link above
	space = p + len(SP) - len(link_above[level])
	if (space > 0):
		link_above[level] += (' ' * space)
	link_above[level] += link_char
	# Fill in to right
	if (node.right):
		draw_node(output, link_above, node.right, level + 1, len(output[level]),'R')
  
def display_tree(root):
	if (root == None):
		print("\tNone")
	h = height(root)
	output = []
	link_above = []
	for i in range(0,h): 
				output.append("")
				link_above.append("")
	draw_node(output, link_above, root, 0, 5, ' ')
	# Create link lines
	for i in range(h):
		for j in range(len(link_above[i])):
			if (link_above[i][j] != ' '):
				size = len(output[i - 1])
				if (size < j + 1):
					output[i - 1] += " " *(j + 1 - size)
				jj = j
				if (link_above[i][j] == 'L'):
					while (output[i - 1][jj] == ' '):
						jj += 1
					for k in range(j+1, jj-1):
						str1 = output[i - 1]
						list1 = list(str1)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
				elif(link_above[i][j] == 'R'):
					while (output[i - 1][jj] == ' '):
						jj-=1
					
					# k = j-1
					for k in range(j-1,jj+1,-1):
						temp = output[i - 1]
						list1 = list(temp)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
						k = k - 1
      
				str1 = link_above[i]
				list1 = list(str1)
				list1[j] = '|'
				link_above[i] = ''.join(list1)
					
	# Output
	for i in range(h):
		if (i):
			print("\t" , link_above[i])
		print("\t" , output[i])
def connect_level_order_siblings(root):
  if root is None:
    return
  queue = deque()
  queue.append(root)
  iteration = 0
  while queue:
    previousNode = None
    levelSize = len(queue)
    print("\tIteration: ", iteration+1)
    iteration +=1
    print("\t\tpreviousNode: ",previousNode)
    print("\t\tlevelSize: ",levelSize)
    # connect all nodes of this level
    for _ in range(levelSize):
      currentNode = queue.popleft()
      print("\t\tcurrentNode: ",currentNode)
      if previousNode:
        print("\t\t\tSetting previousNode.next to currentNode")
        previousNode.next = currentNode
        print("\t\t\tpreviousNode.next: ",currentNode)
      previousNode = currentNode
      print("\t\tpreviousNode: ",previousNode)
      # insert the children of current node in the queue
      if currentNode.left:
        queue.append(currentNode.left)
      if currentNode.right:
        queue.append(currentNode.right)
      print("\t\t",queue)
def main():
  #Tree 1
  root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
  root.left.left = TreeNode(9)
  root.right.left = TreeNode(10)
  root.right.right = TreeNode(5)
  #Tree 2
  root2 = TreeNode(1)
  root2.left = TreeNode(2)
  root2.left.left = TreeNode(3)
  root2.left.right = TreeNode(3)
  root2.right = TreeNode(2)
  root2.right.left = TreeNode(4)
  root2.right.right = TreeNode(4)
  trees = [root,root2]
  for tree in trees:
	  print("Input Tree: ")
	  display_tree(tree)
	  connect_level_order_siblings(tree)
	  print("-"*100+"\n")
main()