Trees

March 01, 2021

Leetcode problems using tree data structures.

94. Binary Tree Inorder Traversal - Left, Node, Right

I: root = [1,null,2,3]
O: [1,3,2]

• We create an empty results array (arr)
• We create a stack an append the root
• While our stack exists we take root and assign it to our node variable for assessing
• Check if node exists
• Check is it’s an instance of our TreeNode sub-class
• Then we append our node’s right child, the current node’s value, and then the node’s left child
  • we add to the stack in the opposite way that the traversal method is assessed
  • when we pop the nodes off the stack they’ll then be in order, so must be added in reversed
  • LIFO = Last In, First Out
• Else case once we reach a null left
  • we will add the node, previously added to our stack, and then append to our output array (res)
• Return our res array

def inorderTraversal(self, root: TreeNode) -> List[int]:
  res = []
  stack = [root]
  while stack:
  node = stack.pop()
  if node:
    if isinstance(node, TreeNode):
      stack.append(node.right)
      stack.append(node.val)
      stack.append(node.left)
    else:
      res.append(node)
  return res

100. Same Tree

I: p = [1,2,3], q = [1,2,3]
O: True

• We check our base cases:
  • if there’s no p node and there’s not q node it’s True
    • they’re both equally empty and therefore technically the same
  • if there’s no p node OR there’s not q node it’s False
  • then we check the value of p’s root and q’s root, if the values aren’t the same it’s False
• After those 3 checks, we recursively call the function to run these 3 checks on again on:
  • p’s next left node against q’s next left node
  • p’s next right node against q’s next right node
• This will end when we run out of nodes and we’ll end with either a True or False value

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
  if not p and not q:
    return True
  if not q or not p:
    return False
  if p.val != q.val:
    return False
  return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

101. Symmetric Tree

I: [1,2,2,3,4,4,3]
O: True

• We use a helper function and pass the first left & right node to it to check our base cases:
  • if there’s no leftNode node and there’s not rightNode node it’s True
  • if there’s no leftNode node OR there’s not rightNode node it’s False
• After those checks, we recursively call this helper function to run these checks again on:
  • leftNode’s left node against rightNode’s right node
  • leftNode’s right node against rightNode’s left node
  • but we verify first that the next node’s values are the same
• This will end when we run out of nodes and we’ll end with either a True or False value

def treeHelper(leftNode, rightNode):
  if not leftNode and not rightNode: return True
  if not leftNode or not rightNode: return False

  return (leftNode.val == rightNode.val) and
  treeHelper(leftNode.left, rightNode.right) and
  treeHelper(rightNode.left, leftNode.right)

class Solution:
  def isSymmetric(self, root: TreeNode) -> bool:
    return treeHelper(root.left, root.right)

102. Binary Tree Level Order Traversal - (Breadth First Search)

I: root = [3,9,20,null,null,15,7]
O: [[3],[9,20],[15,7]]

• Initialize an empty result array for the final result
• Create a queue from Python’s Colletions data structure containter
• Initialize the queue by adding the root
• Begin the while loop, so while the queue is not empty we:
  • Create a qLen variable equal to len(q) to ensure we iterate 1 level at a time
  • Create an empty level array for the current-level node we’ll add to it
  • Next we’ll iterate over the range of nodes on each level, popping the left once first
  • If there’s a node (i.e. not null) we:
    • append that node’s value to our level array
    • add our left child node and right child node to our queue
  • Then, we check if a level even exists in our tree (this accounts for null nodes) before finally appending it to our final result array
• Finally, we return our final result array

def levelOrder(self, root: TreeNode) -> List[List[int]]:
  res = [] # array for result

  q = collections.deque() # import queue (double-ended queue)
  q.append(root) # add root to queue

  while q: # while queue is non-empty
    qLen = len(q) # ensures we iterate 1 level at a time
    level = [] # with nodes from that level, we add to their own list
    for i in range(qLen): # we add the items from all our lists to the result list for totla
      node = q.popleft() # First In First Out
      if node: # check that its not null
        level.append(node.val) # add node to our curr-level array
        q.append(node.left) # add its children to be added next
        q.append(node.right) # add its children to be added next
    if level: # accounts for null nodes
      res.append(level) # after we've processed all nodes on level, add our level results to our result array
  return res

108. Convert Sorted Array to Binary Search Tree

I: nums = [-10,-3,0,5,9]
O: [0,-3,9,-10,null,5]

• We check if the array nums exists
• Then we set a midpoint by diving the length of our array and diving it by 2
  • we use // in Python because we want an integer (no decimal points)
• Now our node is set to this mid tree node
• We recursively call our function with the left child being everything to the left of the mid node
  • and the right being everything to the right of the mid, starting at 1 node after mid, to not include it
• Return node

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
  if not nums:
    return None
  mid = len(nums)//2
  node = TreeNode(nums[mid])
  node.left = self.sortedArrayToBST(nums[:mid])
  node.right = self.sortedArrayToBST(nums[mid+1:])
  return node

111. Minimum Depth of Binary Tree

I: root = [3,9,20,null,null,15,7]
O: 2

• We check if there’s a root to begin with
• Next we check if we’re dealing with a skewed tree
  • if we are then we return the max depth of this skewed tree
  • we only have one “wing” so the min is the max (nothing to compare it to)
• if not a skewed tree (i.e. a regular tree), then we add 1 on each function call and recursively call the function passing the next left and right node to it.
• we return that number

def minDepth(self, root: TreeNode) -> int:
  if not root: return 0
  if not root.left or not root.right:
    return 1+ max(self.minDepth(root.left), self.minDepth(root.right))
  return 1+ min(self.minDepth(root.left), self.minDepth(root.right))

144. Binary Tree Preorder Traversal - Node, Left, Right

I: rroot = [1,null,2,3]
O: [1,2,3]

• We create an empty results array (arr)
• We create a stack an append the root
• While our stack exists we take root and assign it to our node variable for assessing
• Check if node exists
• Check is it’s an instance of our TreeNode sub-class
• Then we append our node’s right child, the node’s left child, and then the current node’s value
  • we add to the stack in the opposite way that the traversal method is assessed
  • when we pop the nodes off the stack they’ll then be in order, so must be added in reversed
  • LIFO = Last In, First Out
• Else case once we reach a null left
  • we will add the node, previously added to our stack, and then append to our output array (res)
• Return our res array

def preorderTraversal(self, root: TreeNode) -> List[int]:
  res = []
  stack = [root]
  while stack:
    temp = stack.pop()
    if temp:
      if isinstance(temp, TreeNode):
        stack.append(temp.right)
        stack.append(temp.left)
        stack.append(temp.val)
      else:
        res.append(temp)
  return res

145. Binary Tree Postorder Traversal - Left, Right, Node

I: rroot = [1,null,2,3]
O: [1,2,3]

• We create an empty results array (arr)
• We create a stack an append the root
• While our stack exists we take root and assign it to our node variable for assessing
• Check if node exists
• Check is it’s an instance of our TreeNode sub-class
• Then we append our node’s right child, the node’s left child, and then the current node’s value
  • we add to the stack in the opposite way that the traversal method is assessed
  • when we pop the nodes off the stack they’ll then be in order, so must be added in reversed
  • LIFO = Last In, First Out
• Else case once we reach a null left
  • we will add the node, previously added to our stack, and then append to our output array (res)
• Return our res array

def postorderTraversal(self, root: TreeNode) -> List[int]:
  res = []
  stack = [root]
  while stack:
    temp = stack.pop()
    if temp:
      if isinstance(temp, TreeNode):
        stack.append(temp.val)
        stack.append(temp.right)
        stack.append(temp.left)
      else:
        res.append(temp)
  return res

226. Invert Binary Tree

I: [4,2,7,1,3,6,9]
O: [4,7,2,9,6,3,1]

• We check if there’s a root to begin with
• Next we swap the left node with the right node
• Then we recursively call the function with each consecutive left & right node
  • invertTree(root.left)
  • invertTree(root.right)
• return the root

def invertTree(self, root: TreeNode) -> TreeNode:
  if root:
    root.left,root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
  return root

637. Average Levels of Binary Tree

I: [4,2,7,1,3,6,9]
O: [4,7,2,9,6,3,1]

• Initialize an empty result array for the final result
• Create a queue from Python’s Colletions data structure containter
• Initialize the queue by addding the root
• Being the while loop, so while the queue is not empty we:
  • Create a qLen variable equal to len(q) to ensure we iterate 1 level at a time
  • Create an empty level array for the current-level node we’ll add to it
  • Next we’ll iterate over the range of nodes on each level, popping the left once first
  • If there’s a node (i.e. not null) we:
    • append that node’s value to our level array
    • add our left child node and right child node to our queue
  • Then, we check if a level even exists in our tree (this accounts for null nodes) before finally appending the level’s average (sum of list divided by length of list) to our final result array
• Finally, we return our final result array

def averageOfLevels(self, root: TreeNode) -> List[float]:
  res = []
  q = collections.deque()
  q.append(root)

  while q:
    qLen = len(q)
    level = []
    for i in range(qLen):
      node = q.popleft()
      if node:
        level.append(node.val)
        q.append(node.left)
        q.append(node.right)
    if level:
      res.append(sum(level)/len(level))
  return res

Written by Christian Turner
Follow me on Twitter

• ← Two Pointer
• Misc. Leetcode →