inorder traversal of tree

Question

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.

trincot · Accepted Answer · 2017-05-09 16:20:26Z

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)

Collectives™ on Stack Overflow

inorder traversal of tree

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related