CODEWITHSUNDEEP
pythonalgorithmtreebinary-tree
codyc4321
codyc4321

Reputation: 9682

How to recursively walk a binary tree?

I have the following question for a quiz I couldn't solve:

Given a tree represented (5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None)))), where the first item is the node, the second item is a left branching tree, and the third item is a right branching tree, find the largest zigzag (option to change direction in the tree).

So this tree starts at 5, goes left to 3 or right to 10, from 3 it would go left to 20 (it can't go right, right is None). Walking from 10 it can go left to 1, or right to 15, etc

I failed it as I was having problems even recursively walking a tree. I couldn't determine how to choose to walk left or right, and when walking the tree the second, third, etc time, how do know it was walked that path before?

I had here

 class Tree(object):

     def __init__(self, zigzags, node, left, right):
         self.zigzags = zigzags
         self.node = node
         self.left = left
         self.right = right

TREE = (5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))



def walk_tree(tree, current_direction='l', zigzag_count=0, this_path=''):
    left = tree[1]
    right = tree[2]

    print('left:')
    print(left)

    print('right:')
    print(right)

    print('zigzag_count:')
    print(zigzag_count)

    possible_left_path = this_path + 'l'  # say like 'lrl'
    possible_right_path = this_path + 'r' # say like 'lrr'

    if left:
        if current_direction == 'r':
            zigzag_count += 1
        return walk_tree(left, 'l', zigzag_count)

    elif right:
        if current_direction == 'l':
            zigzag_count += 1
        return walk_tree(right, 'r', zigzag_count)

    else:
        return zigzag_count

count = walk_tree(TREE)
print(count)

Which I believed walked down the left side then stopped:

$ ./exam_question_2.py 
left:
(3, (20, (6, None, None), None), None)
right:
(10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None)))
zigzag_count:
0
left:
(20, (6, None, None), None)
right:
None
zigzag_count:
0
left:
(6, None, None)
right:
None
zigzag_count:
0
left:
None
right:
None
zigzag_count:
0
0

The expected answer is 2, walking right, right, left, right.

I want to try to solve the zigzagging just to learn, but I'd like to know how to just recursively walk this binary tree in this format, and know when I change walks (when I start at the top again), and some theory behind it if possible. I'd prefer an example in Python or JavaScript.

Upvotes: 2

Views: 1346

Answers (2)

user1196549
user1196549

Reputation:

Adopting a recursive approach, you can state the following rule:

Le longest zigzag from the current node, if reached from the left, is the longest between the longest left zigzag and the longest right zigzag plus one; and conversely if reached from the right.

The rule differs for the root node, as it is not reached from any side.

def Length(Node, FromLeft):
  if Node == None:
    return 0
  return max(Length(Node.Left, True) + (1 if not FromLeft else 0), Length(Node.Left, False) + (1 if FromLeft else 0))

print max(Length(Root.Left, True), Length(Root.Right, False))

I made no use of the zigzag field, but of course this is doable.

Upvotes: 1

Martijn Pieters
Martijn Pieters

Reputation: 1124708

This is a typical divide-and-conquer problem. Given a node with children, the zigzag score for that node is that of the child with the highest zigzag score (with 1 added if reaching that child required a change of direction):

def zigzagscore(node):
    left, right = node[1:]

    left_zigzag, left_path = 0, ''
    if left is not None:
        left_zigzag, left_path = zigzagscore(left)
        if left_path.startswith('r'):
            # We zigged for left
            left_zigzag += 1
        left_path = 'l' + left_path

    right_zigzag, right_path = 0, ''
    if right is not None:
        right_zigzag, right_path = zigzagscore(right)
        if right_path.startswith('l'):
            # We zagged for right
            right_zigzag += 1
        right_path = 'r' + right_path

    if left_zigzag > right_zigzag:
        return left_zigzag, left_path
    else:
        return right_zigzag, right_path

Your code never considered the right path when there is a left node available.

This produces your expected path:

>>> TREE = (5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))
>>> zigzagscore(TREE)
(2, 'rrlr')

Upvotes: 4

Related Questions