Tony Wang Tony Wang - 1 month ago 8
Python Question

cofusing about lookup node with binary tree

I could print my tree in order with

testTree.printInorder(testTree.root)
. I have tried to lookup some node ,and the function
findNode
doesn't work anymore .
print testTree.findNode(testTree.root,20)


whatever I put in just return
None
. so confusing!

class TreeNode:
def __init__(self, value):
self.left = None;
self.right = None;
self.data = value;


class Tree:
def __init__(self):
self.root = None
def addNode(self,node,value):
if node == None:
self.root = TreeNode(value)
else:
if value < node.data:
if node.left == None:
node.left = TreeNode(value)
else:
self.addNode(node.left,value)
else:
if node.right == None:
node.right = TreeNode(value)
else:
self.addNode(node.right,value)

def printInorder(self,node):
if node != None:
self.printInorder(node.left)
print node.data
self.printInorder(node.right)

def findNode(self,node,value):
if self.root != None:
if value == node.data:
return node.data
elif value < node.data and node.left != None:
self.findNode(node.left,value)
elif value > node.data and node.right != None:
self.findNode(node.right,value)
else:
return None
testTree = Tree()
testTree.addNode(testTree.root, 200)
testTree.addNode(testTree.root, 300)
testTree.addNode(testTree.root, 100)
testTree.addNode(testTree.root, 30)
testTree.addNode(testTree.root, 20)
#testTree.printInorder(testTree.root)
print testTree.findNode(testTree.root,20)

Answer

Any function without an explicit return will return None.

You have not returned the recursive calls within findNode. So, here.

if value == node.data:
    return node.data
elif value < node.data and node.left != None:
    return self.findNode(node.left,value)
elif value > node.data and node.right != None:
    return self.findNode(node.right,value)

Now, I can't help but thinking this is a bit noisy. You'll always start adding from the root, yes?

testTree.addNode(testTree.root, 200)

You could rather do this

testTree.addNode(200)

And to do that, you basically implement your methods on the TreeNode class instead. So, for the addNode.

You could also "return up" from the recursion, rather than "pass down" the nodes as parameters.

class TreeNode:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.data = value

    def addNode(self,value):
        if self.data == None:  # Ideally, should never end-up here
            self.data = value
        else:
            if value < self.data:
                if self.left == None:
                    self.left = TreeNode(value)
                else:
                    self.left = self.left.addNode(value)
            else:
                if self.right == None:
                    self.right = TreeNode(value)
                else:
                    self.right = self.right.addNode(value)

        return self # Return back up the recursion

Then, in the Tree class, just delegate the addNode responsibility to the root

class Tree:
    def __init__(self):
        self.root = None

    def addNode(self,value):
        if self.root == None:
            self.root = TreeNode(value)
        else:
            self.root = self.root.addNode(value)