Teaching Kids Programming – Sibling Node in a Binary Search Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an integer k and a binary search tree root, where each node is either a leaf or contains 2 children. Find the node containing the value k, and return its sibling’s value.

You can assume that the solution always exists (e.x. root won’t have value of k)

Constraints
n ≤ 100,000 where n is the number of nodes in root

  1
 / \
2   3

The silbing node of 2 is 3, and vice versa

Iterative Algorithm to Locate the Sibling Node in Binary Tree

By comparing the current root node with the target node, we can either go to left tree or right tree. And at the same time, we remember the sibling node in case the next node is the target. Assuming the Binary Search Tree is highly balanced, the time complexity is O(LogN).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root, k):
        sib = -1
        while root:
            if k < root.val:
                sib = root.right.val
                root = root.left
            elif k > root.val:
                sib = root.left.val
                root = root.right
            else:
                return sib
        return sib

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root, k):
        sib = -1
        while root:
            if k < root.val:
                sib = root.right.val
                root = root.left
            elif k > root.val:
                sib = root.left.val
                root = root.right
            else:
                return sib
        return sib

Recursive Algorithm to Locate the Sibling Node in Binary Tree

We can also do this using Recursion. Compared to Search a Node in Binary Search Tree, we also pass along the sibling node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root, k):
        def dfs(root, sib, k):
            if root.val == k:
                return sib
            if k < root.val:
                return dfs(root.left, root.right.val, k)
            return dfs(root.right, root.left.val, k)
        return dfs(root, -1, k)

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root, k):
        def dfs(root, sib, k):
            if root.val == k:
                return sib
            if k < root.val:
                return dfs(root.left, root.right.val, k)
            return dfs(root.right, root.left.val, k)
        return dfs(root, -1, k)

See also the C++ implementation to retrieve the sibling node in a binary (search) tree: Algorithms to Compute the Sibling Value in Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —