Binary Tree Inorder Traversal - query

Question

I am looking at LeetCode problem 94. Binary Tree Inorder Traversal:

Given the root of a binary tree, return the inorder traversal of its nodes' values.

For the above problem I tried the following code:

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        list1=[]
        if root==None:
            return None
            inorderTraversal(root.left)
            list1.append(root.val)
            inorderTraversal(root.right)
        print(list1)
        return list1

But it fails the most simple test cases, and gives errors.

I found a working solution:

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        list1=[]
        if root==None:
            return None
        def create_list(root,list1):
            if root==None:
                return
            create_list(root.left,list1)
            list1.append(root.val)
            create_list(root.right,list1)
        create_list(root,list1)
        print(list1)
        return list1

What is wrong with my code?

I would like to better understand how recursion works for Binary Trees. I can solve basic problems, but as the problem statement gets tougher, it gets hard to imagine/dry run what recursion would return.

Answer 1

These are the issues with the non-working code:

• inorderTraversal is not a known function. It should be self.inorderTraversal so you access the method.

• You have some dead code, as the statements after return None will never execute. The concerned statements should not be part of the if block and have less indentation

• self.inorderTraversal should not return None. If the tree is empty, you should return an empty list, not None.

• self.inorderTraversal returns a list, but you ignore the lists that are returned from the recursive calls. That means you lose information and those recursive calls do all their work for nothing. Instead, build the current list from those lists coming back from recursion.

Here is what the code would look like if those issues are corrected:

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        list1 = []
        if root is None:
            return []
        list1 = self.inorderTraversal(root.left)
        list1.append(root.val)
        list1.extend(self.inorderTraversal(root.right))
        return list1

This solution is however not memory efficient, as it keeps creating new lists from existing lists. A more pythonic way would be to create a generator function and collect the yielded values into one list:

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def iterate(node):
            if node:
                yield from iterate(node.left)
                yield node.val
                yield from iterate(node.right)
        
        return list(iterate(root))

Answer 2

Steps for inorder traversal of a binary tree:

1. First traverse till last node in left branch of every next node.
2. Return when None node found
3. Append current element to in order list
4. At this point this means we traversed all left possible nodes.
5. Now go to right branch and do the same.
6. Print the inorder list.

Time complexity: O(N)
Space complexity: O(N)

class Solution:
    def inorderPrint(self, node, res):
        if node==None:
            return res
        self.inorderPrint(node.left,res)
        res.append(node.val)
        self.inorderPrint(node.right,res)
        
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        self.inorderPrint(root,res)
        return res