LeetCode 700. Search in a Binary Search Tree

Question

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}}

The return value of the recursive calls to "dfs" must in turn be returned (if not None) to the calling "dfs" so it is again returned through the recursive calls until the calling "searchBST" is reached. — Michael Butscher
– Michael Butscher, Commented Mar 22, 2021 at 2:02
@pavel You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null. — Clayton C.
– Clayton C., Commented Mar 22, 2021 at 2:06
@MichaelButscher I was under the impression that only one of those would execute then — Clayton C.
– Clayton C., Commented Mar 22, 2021 at 2:08
@ClaytonC. On first call (left subtree) you have to check if a valid node is returned. If so, the second call (right subtree) is unnecessary. If not, continue with second call where you can return the return value unconditionally. — Michael Butscher
– Michael Butscher, Commented Mar 22, 2021 at 3:57

Michael Butscher · Accepted Answer · 2021-03-22 23:12:03Z

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.

Collectives™ on Stack Overflow

LeetCode 700. Search in a Binary Search Tree

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related