Traverse a binary tree using dfs, stopping at a given point (in Python)

Question

I'm learning about some basic computer science concepts. As a demo, I'm creating a script in Python that will perform various functions on a binary tree. I've been able to successfully program most of these functions, except for one specific one.

For a binary tree created from an array of integers, I would like to do a depth first search for an integer, and return the path that was taken through the tree up until that integer was found as an array (with the last number in that array being the number that was being searched for). As soon as the first match for that integer is found, I want to stop traversing the tree.

For example, for an inorder dfs of array [3,2,4,1,4,6,8,5] for integer 4, it should return [1,2,3,4]

For integer 5 it should return [1,2,3,4,4,5] etc.

Here is my code:

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

    def getValue(self):
        return self.value

def buildTree(array):
    print("building tree....")
    root=Node(array[0])
    del(array[0])
    for a in array:
        insert(root,Node(a))
    print("building complete")
    return root

def insert(root,node): 
    if root is None: 
        root = node 
    else: 
        if root.value < node.value: 
            if root.right is None: 
                root.right = node 
            else: 
                insert(root.right, node) 
        else: 
            if root.left is None: 
                root.left = node 
            else: 
                insert(root.left, node) 

def depthFirstSearch(root,target,results,subSearch):
#0:preorder
#1:inorder
#2:postorder
    if root!=None:

        if subSearch==0:
            results.append(root.getValue())
            if root.getValue()==target:
                return results

        depthFirstSearch(root.left,target,results,subSearch)

        if subSearch==1:
            results.append(root.getValue())
            if root.getValue()==target:
                return results

        depthFirstSearch(root.right,target,results,subSearch)

        if subSearch==2:
            results.append(root.getValue())
            if root.getValue()==target:
                return results

    return results

if __name__ == '__main__':
    #stuff that gets our arguments
    #...
    array=[3,2,4,1,4,6,8,5] #we would actually get this as an argument, but using this for example array
    target=4 #example target
    subSearch=1 #using inorder traversal for this example

    root=buildTree(array)
    results=[]
    results=depthFirstSearch(root,target,results,subSearch) 
    print(results) #expected:[1,2,3,4]

I tried various solutions, besides simply "return results" upon finding the target, however I was unable to find one that worked. So, I used that for sake of simplicity. — Zachary Rodriguez
– Zachary Rodriguez, Commented Feb 20, 2019 at 8:22
Also, I do not want to traverse the entire tree and simply only print the array up until the target. I want to actually terminate the search! — Zachary Rodriguez
– Zachary Rodriguez, Commented Feb 20, 2019 at 8:26
Please post a Minimal, Complete and Verifiable example. The variables you use are not defined (array, target,subSearch). — Lomtrur
– Lomtrur, Commented Feb 20, 2019 at 8:27
It looks like you are confusing an array with a binary tree. Your depthFirstSearch() function is expecting a root that is supposedly an instance of the class Node. But in your call to depthFirstSearch you are passing the first element of an array of integers to it instead. You have depthFirstSearch(array[0], ...). The first thing you'll need to do is to convert your array to a binary tree consisting of Nodes. — darksky
– darksky, Commented Feb 20, 2019 at 8:44
It's because I screwed up when I was making this post. I added the functions used to build the tree. — Zachary Rodriguez
– Zachary Rodriguez, Commented Feb 20, 2019 at 10:33

anand_v.singh · Accepted Answer · 2019-02-20 15:40:26Z

Okay this is easy, just use an Additional variable flag and then your function becomes

def depthFirstSearch(root,target,results,subSearch, flag = 0):
#0:preorder
#1:inorder
#2:postorder
    if root!=None:

        if subSearch==0:
            results.append(root.getValue())
            if root.getValue()==target:
                return results, 1

        results, flag =depthFirstSearch(root.left,target,results,subSearch)
        if flag == 1:
            return results, flag
        if subSearch==1:
            results.append(root.getValue())
            if root.getValue()==target:
                return results, 1

        results, flag = depthFirstSearch(root.right,target,results,subSearch)
        if flag == 1:
            return results, flag

        if subSearch==2:
            results.append(root.getValue())
            if root.getValue()==target:
                return results, 1

    return results, flag

Here Flag changes to one and that is propagated as the function stack shrinks, keeping them after each recursive calls takes care of this.

Also in main function, the function call becomes

results, _=depthFirstSearch(root,target,results,subSearch)

Since flag = 0 is present in function definition you just need to discard the second variable, you can even use that to check if the element was found in the tree rather than just printing the whole tree if element is not present.

If you have any doubts or concerns, comment below.

Collectives™ on Stack Overflow

Traverse a binary tree using dfs, stopping at a given point (in Python)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related