# How To Get Sibling Node In Binary Search Tree If There Is No Left Child In A Node

## 31 January 2022 - 1 answer

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

``````

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)
``````

I also put the graph illustration in the following:

Edit: what you are looking for is called deapth 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.