CODEWITHSUNDEEP
pythontreetraversal
Sly Cooper
Sly Cooper

Reputation: 79

traversing through a tree

I want to write a function which returns all the elements in a tree in a list. I'm not allowed to use global variables though. Here's what I tried:

def traverse(current node):    
    if no left child and no right child:
        return current nodes data
    else:
        if both left child and right child exist:
            return [current nodes data,left_child.traverse(),right_child._traverse()]
        elif no left child:   return [current node's data,right_child.traverse()]
        elif no right child:  return [current node's data,left_child.traverse()]

we used this example: (root is 2, left child is 1, right child is 3 and right child of right child is 4)

    2
1      3
          4

calling traverse on this tree returned this:

[2, 1, [3, 4]]

So the only problem is that we can't get it all to fit within just one list.

EDIT: Here are some of the node functions which can be called: node.data, node.left, node.right

Upvotes: 0

Views: 962

Answers (2)

Moshe
Moshe

Reputation: 9899

The issue is that each function call is creating a new list and appending it to existing list. Instead, you want to add the child nodes to the existing list.

Here is a recursive solution that doesn't rely on explicitly passing a list between calls:

def traverse(node):
    if node.left and node.right:
        return [node.data] + traverse(node.left) + traverse(node.right)
    elif node.left:
        return [node.data] + traverse(node.left)
    elif node.right:
        return [node.data] + traverse(node.right)
    else:
        return [node.data]

Upvotes: 0

Sergiu Toarca
Sergiu Toarca

Reputation: 2759

Instead of returning a list of values, you want to pass in an array and recursively append the values to the array:

def traverse(node, arr):
    if node.left:
        traverse(node.left, arr)
    arr.append(node.data)
    if node.right:
        traverse(node.right, arr)
    return arr # this is for convenience so we don't have to store arr

You would get the list by calling:

traverse(node, [])

Upvotes: 2

Related Questions