Traverse tree and return a node instance after n traversals in python

Question

The end goal is to copy a node from one tree to another tree. I want to visit each node in a binary tree and return a node instance after a number of traverses. I cannot seem to figure out how to return a specific node. Every time the node returned matches the id of the root node since I pass the root node to the function.

class node():

    def __init__(self):
        self.parent = None
        self.left = None
        self.right = None

    def randnode(self, target):
        global count
        if target == count:
            # print 'At target', '.'*25, target
            return self
        else:
            if self.left is not None:
                count += 1
                self.left.randnode(target)
            if self.right is not None:
                count += 1
                self.right.randnode(target)

First and foremost, you need to return the result of the recursive call. `return self.left.randnode(target)` and `self.right.randnode(target)`. You might also like to check [this answer](http://stackoverflow.com/a/30214677/1903116) on recursion. — thefourtheye, Oct 14 '15 at 15:02
Can you add your sample data + calls to this function for trying out possible solutions ? — Jiby, Oct 14 '15 at 15:10

Jiby · Answer 1 · 2015-10-14T15:18:42.913

If you're doing a DFS and counting iterations, you don't even need recursion, just a stack of places to try, and popping/pushing data.

def dfs(self,target):
    count = 0
    stack = [start]
    while stack:
        node = stack.pop()
        if count == target:
            return node

        if node is None:    # since we push left/right even if None
            continue        # stop pushing after we hit None node
        stack.extend([self.left,self.right])
    return -1  # ran out of nodes before count

Bonus points : swapping stack to a queue for BFS

Apart from that, you might want to pass the count as a parameter, like all self-respecting recursive calls, you can make this stateless ;-)

class node():

    def __init__(self):
        self.parent = None
        self.left = None
        self.right = None

    def randnode(self, target,count=0):
        if target == count:
            # print 'At target', '.'*25, target
            return self
        if self.left is not None:
            return self.left.randnode(target,count + 1)
        if self.right is not None:
            return self.right.randnode(target,count + 1)

Traverse tree and return a node instance after n traversals in python

1 Answers1