Friedrich Ewald My Personal Website

Leetcode: Populate next pointers in tree

Given a perfect binary search tree, connect all the nodes to the node on their right The solution is to do breadth-first-search in an iterative fashion. This puts all the nodes at the same level in a queue. By iterating over the queue we can connect each node to its successor. During this process we add the children of each node as the next entry. We repeat this process until the queue is empty.

class Node:
  def __init__(self, val=0, left=None, right=None, next=None):
    self.val = val
    self.left = left
    self.right = right
    self.next = next

  def __repr__(self) -> str:
    return f'{self.val}'

class Solution:
  def connect(self, root):
    queue = [[root]]

    while len(queue) > 0:
      for i in range(len(queue[0]) - 1):
        queue[0][i].next = queue[0][i+1]

      queue.append([])
      
      for i in range(len(queue[0])):
        item = queue[0][i]
        if item.left is not None:
          queue[-1].append(item.left)
        if item.right is not None:
          queue[-1].append(item.right)
      
      if len(queue[-1]):
        queue.pop()
        
      queue = queue[1:]
    
    return root


if __name__ == '__main__':
  s = Solution().connect
  r = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
  s(r)
Runtime: 84 ms, faster than 70.50% of Python3 online submissions for Populating Next Right Pointers in Each Node. Memory Usage: 15.8 MB, less than 49.85% of Python3 online submissions for Populating Next Right Pointers in Each Node.


About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.