how to get sibling node in binary search tree if there is no left child in a node

Question

I'm trying to find the node for the first node whose data is greater than the value using recursion, but I found that I cannot go from N3 to N4 if N3 has no left child. Can anyone help me figure out a way to write that part of the code so that I can move to N4, which is the sibling nod of N3? Thank you!

ps: it should search a single path from the root to the leaf before moving to the next leaf, some intended test cases are

print(find(root,100000)) #Returns N8 (node search order N1,N3, N4, N8)
print(find(root,100)) #Returns root
print(find(root,800000)) #Returns N7 (node search order N1, N3, N4, N8, N2, N5, N6, N7 )
print(find(n2,200000)) #Returns N5 (search starts from subtree at N2)

The following code is how to build the tree and my partial code:

#The tree definition
class BinaryTreeNode:
    def __init__(self, name,data):
        self.name = name #The name of the node
        self.data = data #Data associated with the node
        self.leftChild = None #Left child
        self.rightChild = None #Right child
    
    #adds a left and right child to the node. Note that the left child is added first
    #I.e., there may be a left child without a right child but there cannot be a right child without a left child
    def add_children(self,left,right=None): 
        self.leftChild = left
        self.rightChild = right
        
    #str function for printing the contents of a node
    def __str__(self):
        rval = self.name
        if self.leftChild:
            rval += " Left: " + self.leftChild.name
        if self.rightChild:
            rval += " Right: " + self.rightChild.name
        return rval
    
    #repr function for internal representation
    def __repr__(self):
        return self.name

#Code for building the tree
root = BinaryTreeNode("root",33000)
n1 = BinaryTreeNode("N1",55000)
n2 = BinaryTreeNode("N2",120000)
n3 = BinaryTreeNode("N3",72000)
n4 = BinaryTreeNode("N4",88000)
n5 = BinaryTreeNode("N5",224000)
n6 = BinaryTreeNode("N6",56000)
n7 = BinaryTreeNode("N7",920000)
n8 = BinaryTreeNode("N8",183000)


root.add_children(n1,n2)
n1.add_children(n3,n4)
n4.add_children(n8)
n2.add_children(n5)
n5.add_children(n6,n7)

The following is my code to get the node:

def find(node,value):
    if node.data>value: return node.name
    if node.leftChild is not None and node.leftChild.data >value:
        return node.leftChild.name
    if node.leftChild is not None and node.leftChild.data <=value:
        return find(node.leftChild,value)
    else:
# in this part, I think I need to find the sibling node, i.e, go from N3 to N4
        return find(node.rightChild,value)

Answer 1

Edit: what you are looking for is called depth first search (DFS).

There is a problem with your implementation of binary search tree: it does not balance when you insert a new node. This increases the search time to O(n) when it can be O(logn).

If you intend for your tree to be this way, here is the code that will search the entire tree:

def find(node,value):
    if node:  # equivalent to  `if node is not None`
        if node.data > value:
            return node.name
        return find(node.leftChild, value) or find(node.rightChild, value)

    # returns `None` if node is None
    # python will return node.name over None

Note that python will return the first occurance only.