Check if two nodes in a binary tree are siblings

Problem

In a binary tree, two nodes are considered siblings if they both have the same parent node. Given a binary tree and two node values, x and y, write a program to determine if these two nodes are siblings. If the nodes have the same parent, return True, otherwise, return False.

Examples

graph TD;
A(1)
B(2)
C(3)
D(4)
E(5)

A --- B & C
C --- D & E

Example 1

Input: Binary Tree = [1, 2, 3, null, null, 4, 5], x = 4, y = 5
Output: True
Explanation: Nodes 4 and 5 have the same parent (node 3).

Example 2

Input: Binary Tree = [1, 2, 3, null, null, 4, 5], x = 2, y = 5
Output: False
Explanation: Nodes 2 and 5 are not siblings because they do not share the same parent.

Example 3

Input: Binary Tree = [1, 2, 3, null, null, null, null], x = 2, y = 3
Output: False
Explanation: Nodes 2 and 3 have different parents (node 1).

Solution

Method 1 - Using DFS

Sibling nodes are those that share the same parent node in a binary tree.

Approach

1. Traverse the Tree: Start at the root and check if the root has both target nodes x and y as children.
2. Recursive Check:
   • If not found in the current node, recursively check the left and right subtrees of the current node.
3. Base Case:
   • If the node is null, return False.
4. Return Result: Return True if siblings are found; otherwise, return False.

Code

Java

class Solution {
    public boolean areSiblings(TreeNode root, int x, int y) {
        // Base case: If root is null, return false
        if (root == null) {
            return false;
        }

        // Check if the current node's children are x and y
        if (root.left != null && root.right != null) {
            if ((root.left.val == x && root.right.val == y) ||
                (root.left.val == y && root.right.val == x)) {
                return true;
            }
        }

        // Recursively check left and right subtrees
        return areSiblings(root.left, x, y) || areSiblings(root.right, x, y);
    }

    public static void main(String[] args) {
        // Tree: 1 -> [2, 3], 3 -> [4, 5]
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);

        Solution solution = new Solution();
        System.out.println(solution.areSiblings(root, 4, 5)); // Output: true
        System.out.println(solution.areSiblings(root, 2, 5)); // Output: false
    }
}

Python

class Solution:
    def areSiblings(self, root: TreeNode, x: int, y: int) -> bool:
        # Base case: if root is None, return False
        if not root:
            return False
        
        # Check if the current node's children are x and y
        if root.left and root.right:
            if (root.left.val == x and root.right.val == y) or \
            (root.left.val == y and root.right.val == x):
                return True
        
        # Recursively search in left and right subtrees
        return self.areSiblings(root.left, x, y) or self.areSiblings(root.right, x, y)

# Example usage:
# Tree: 1 -> [2, 3], 3 -> [4, 5]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)

solution = Solution()
print(solution.areSiblings(root, 4, 5))  # Output: True
print(solution.areSiblings(root, 2, 5))  # Output: False

Complexity

• ⏰ Time complexity: O(n) . This is because we traverse every node in the binary tree exactly once.
• 🧺 Space complexity: O(h). Here, h is the height of the binary tree. The space is used for recursive calls.