CODEWITHSUNDEEP
pythonbinary-treebinary-search-tree
Luca
Luca

Reputation: 10996

inorder traversal of tree

I am looking at an inorder recursive traversal of a tree implementation and am wondering how I can save the result into a list and return that from the recursive function. I am having issues on how to persist this list during the stack unwinding.

So, I have the code as:

class BinaryTreeNode(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def recursive_inorder(root):
    if not root:
        return

    nodes = list()

    recursive_inorder(root.left)
    nodes.append(root.value)
    print root.value
    recursive_inorder(root.right)
    return nodes

And I call this as:

three = BinaryTreeNode(3)
five = BinaryTreeNode(5)
one = BinaryTreeNode(1)
four = BinaryTreeNode(4)
two = BinaryTreeNode(2)
six = BinaryTreeNode(6)

three.left = five
five.left = one
five.right = four

three.right = two
two.left = six

nodes = recursive_inorder(three)

The nodes are traversed in the right order but I am having trouble figuring out how to save the result into the nodes list.

Upvotes: 0

Views: 988

Answers (1)

trincot
trincot

Reputation: 350137

Use the return value from the recursive call to extend your nodes list. Also, return an empty list when you have a None value, so your function is guaranteed to always return a list:

def recursive_inorder(root):
    if not root:
        return []

    nodes = list()

    nodes.extend(recursive_inorder(root.left))
    nodes.append(root.value)
    nodes.extend(recursive_inorder(root.right))
    return nodes

Or a bit more concise:

def recursive_inorder(root):
    if not root:
        return []

    return recursive_inorder(root.left) + [root.value] + recursive_inorder(root.right)

Upvotes: 1

Related Questions