Inorder Binary Tree Traversal

Question

I created Binary Tree with some nodes and trying to get the result of inorder traversal using dictionary, but It does not really work. Why the list does not append, even tho it prints the result?

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

def inoder(bomj):
    visited = []

    if bomj:
        inoder(bomj.left)
        print(bomj.val)
        visited.append(bomj.val)
        inoder(bomj.right)

    return visited

tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.left.left = TreeNode(4)
tree.left.right = TreeNode(5)
tree.left.left.left = TreeNode(7)
tree.right.left = TreeNode(6)
print(inoder(tree))

Result:
7
4
2
5
1
6
3
[1]

I also tried using dictionary

Answer 1

You are resetting internal every time you call inorder. You need a variable inorder that's outside the recursion.

def inorder(bomj):
    visited = []

    def internal(bomj):
        if bomj:
            internal(bomj.left)
            print(bomj.val)
            visited.append(bomj.val)
            internal(bomj.right)

    internal(bomj)
    return visited

Answer 2

Without changing the code too much, you can just merge the list:

def inoder(bomj):
    visited = []

    if bomj:
        left = inoder(bomj.left)
        print(bomj.val)
        right = inoder(bomj.right)
        visited = left + [bomj.val] + right

    return visited

Answer 3

You can pass the data structure to collect the values by reference as a parameter argument.

Updated code:

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

def inorder(bomj):
    visited = []
    _inorder(bomj, visited)
    return visited

def _inorder(bomj, nodes):
    if bomj:
        _inorder(bomj.left, nodes)
        nodes.append(bomj.val)
        _inorder(bomj.right, nodes)

tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.left.left = TreeNode(4)
tree.left.right = TreeNode(5)
tree.left.left.left = TreeNode(7)
tree.right.left = TreeNode(6)
print(inorder(tree))

Result:

[7, 4, 2, 5, 1, 6, 3]