CODEWITHSUNDEEP
pythonrecursionsearchbinary-search-treedepth-first-search
Clayton C.
Clayton C.

Reputation: 881

LeetCode 700. Search in a Binary Search Tree

I am trying to do a preorder DFS on a BST for a LeetCode problem, but cannot seem to get the recursive solution. My iterative solutions are fine (both BFS and DFS), but the recursive one keeps returning an empty node even after finding it in the tree. Here is my code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:

    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        def dfs(node):
            if node:
                if node.val == val: 
                    print("found:",node)
                    return node
                dfs(node.left)
                dfs(node.right)
        return dfs(root)

My print statement in the nested function finds the node and returns the correct node/subtree (as shown below), but it does not translate to the outer function. Any ideas? Thanks!

found: TreeNode{val: 2, left: TreeNode{val: 1, left: None, right: None}, right: TreeNode{val: 3, left: None, right: None}}

Upvotes: 0

Views: 258

Answers (1)

Clayton C.
Clayton C.

Reputation: 881

This answer was c/o of @MichaelButscher. I needed to be returning the left node until it was null, then return the right node. Previously, I was just calling dfs without a return statement, so the function was getting killed after traversing the left-most branch.

Here is the updated code:

class Solution:

    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        def dfs(node):
            if node:
                if node.val == val: 
                    print("found:",node)
                    return node
                left = dfs(node.left)
                if left: return left # <-- Needed this return statement
                right = dfs(node.right)
                return right # <-- Needed this return statement
        return dfs(root)

Additionally, I know that this is obviously not the optimal way to search through a binary tree, as this takes O(n) time as opposed to O(log(n)), but I wanted to practice some BST DFS.

Upvotes: 1

Related Questions