Algorithms to Compute the Sibling Value in Binary Tree

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

Sibling Tree Value using Hash Table and Depth First Search Algorithm

For any Binary Tree, we can record the sibling node when we visit each parent node in a hash map. We can do Breadth First Search Algorithm or Depth First Search Algorithm to Traverse the binary tree.

Below C++ code traverse the tree using DFS and map each Node to its sibling node:

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int getSiblingNode(Tree* root, int k) {
    unordered_map<int, int> sibling;
    function<void(Tree* root)> dfs = [&](Tree* root) {
        if (!root) return;
        if (root->left && root->right) {
            sibling[root->left->val] = root->right->val;
            sibling[root->right->val] = root->left->val;
        }
        dfs(root->left);
        dfs(root->right);
    };
    dfs(root);
    return sibling[k];
}

The time complexity is O(N) and the space complexity is O(N).

Sibling Tree Node in Binary Search Tree

Given the tree is already a binary search tree and in fact each node will either be a leaf node or having two children. Thus we can traverse the binary search tree in O(LogN) time on average assuming the binary search tree is balanced.

If we find the target node, we return the sibling value which is parent’s other kid. We can record/update this when we visit the parent node.

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int getSiblingNode(Tree* root, int k) {
    int sib = -1;
    while (root) {
        if (root->val == k) {
            return sib;
        }
        if (k > root->val) {
            sib = root->left->val;
            root = root->right;
        } else {
            sib = root->right->val;
            root = root->left;
        }
    }
    return sib;
}

The time complexity is O(LogN) and the space complexity is O(1) constant. See also the Recursive algorithm to find the sibling node in a binary tree: Teaching Kids Programming – Sibling Node in a Binary Search Tree

–EOF (The Ultimate Computing & Technology Blog) —