CODEWITHSUNDEEP
pythonpython-3.xtree-traversal
Slayer
Slayer

Reputation: 882

How to store value in a list while inorder traversal in a tree?

I have been trying to find an efficient and easy way to store the value of tree traversal (in order) in a list for further processing but I am not getting a proper way to perform it.

The reason I want it is to find the mode in the tree. I have tried global variables but I am not a fan of it, makes the code look bad. I tried the yield function but that doesn't seem to do any good. (I have some hope left for this)

def inorder(self,root):
        if not root:
            return 
        self.inorder(root.left)
        self.store(root.val)
        self.inorder(root.right)

Thanks, Prerit

Upvotes: 2

Views: 755

Answers (1)

falsetru
falsetru

Reputation: 369424

If you're using Pyhotn 3.3+, you can use yield and yield from expressions:

class Node:

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

    def inorder(self, root):
        if not root:
            return
        yield from self.inorder(root.left)
        yield root.val
        yield from self.inorder(root.right)

        # # For Python 3.2-
        # for val in self.inorder(root.left):
        #     yield val
        # yield root.val
        # for val in self.inorder(root.right):
        #     yield val

Usage:

# Traverse
n = Node('top', Node('left'), Node('right'))
for val in n.inorder(n):
    print(val)
# -> prints `left`, `top`, `right`

# get as a list
list(n.inorder(n)) # -> ['left', 'top', 'right']

Upvotes: 1

Related Questions