Friedrich Ewald My Personal Website

Leetcode: Binary tree inorder traversal

The task is to traverse a binary tree inorder. This means, that starting from the root node, nodes should be visited in the following order: left, self, right. With this knowledge it is easy to come up with a recursive algorithm. The only special case that needs to be handled are the leaf nodes that don’t have any children. By still visiting the non-existing children and then returning an empty list ([]) when a None is encountered, the whole algorithm fits into two lines.

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
  def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    # Handle non-existing leaf-nodes (including empty root)
    if root is None:
      return []
    
    # Visit left - current - right
    return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)


if __name__ == '__main__':
  s = Solution().inorderTraversal
  print(s(TreeNode(1, None, TreeNode(2, TreeNode(3), None))), [1,3,2])
Runtime: 41 ms, faster than 70.32% of Python3 online submissions for Binary Tree Inorder Traversal. Memory Usage: 13.8 MB, less than 60.08% of Python3 online submissions for Binary Tree Inorder Traversal.


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.