how to check if two nodes are siblings

Jordan Payton

2 min read

·

06-09-2024

40

0

Share

When working with data structures like trees, it's often important to determine the relationships between nodes. One common relationship is whether two nodes are siblings. Sibling nodes share the same parent, much like brothers and sisters in a family tree. In this guide, we'll explore how to check if two nodes are siblings in a binary tree.

Understanding Sibling Nodes

Before we dive into the process, let’s clarify what it means for two nodes to be siblings. In a binary tree:

• Two nodes are considered siblings if they are children of the same parent node.
• For example, in the tree structure below, nodes 4 and 5 are siblings, while node 2 is not a sibling of nodes 4 and 5.

          1
         / \
        2   3
       / \
      4   5

Steps to Check if Two Nodes are Siblings

Here’s a simple and clear method to determine if two nodes are siblings in a binary tree:

Step 1: Define the Binary Tree Structure

To begin, you'll want to have a clear definition of your binary tree structure. Here's a simple Python class definition for a tree node:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Step 2: Create a Function to Find the Parent Node

Next, you need a way to find the parent of a given node. This function will traverse the tree to locate the parent node:

def find_parent(root, child):
    if root is None:
        return None

    if (root.left == child) or (root.right == child):
        return root

    left_search = find_parent(root.left, child)
    if left_search is not None:
        return left_search
    
    return find_parent(root.right, child)

Step 3: Create the Sibling Check Function

Now, you can combine the findings to check if two nodes are siblings. Here’s how you can do that:

def are_siblings(root, node1, node2):
    if root is None:
        return False
    
    parent1 = find_parent(root, node1)
    parent2 = find_parent(root, node2)

    return parent1 == parent2 and parent1 is not None

Example Usage

Here's an example to see how this works in practice:

# Creating the tree structure
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Checking if 4 and 5 are siblings
print(are_siblings(root, root.left.left, root.left.right))  # Output: True

# Checking if 2 and 3 are siblings
print(are_siblings(root, root.left, root.right))  # Output: False

Summary

In summary, checking if two nodes are siblings in a binary tree involves identifying their parent nodes and comparing them. If both nodes have the same parent, they are siblings. Here’s a quick recap of the process:

1. Define your binary tree structure.
2. Implement a function to find the parent of a node.
3. Use this function to determine if two nodes share the same parent.

This method is straightforward and ensures you can easily ascertain sibling relationships within your binary tree.

Related Articles

• Understanding Binary Trees: A Comprehensive Guide
• Traversing Binary Trees: Depth-First vs. Breadth-First
• Building a Binary Search Tree: Step-by-Step Guide

Feel free to explore these links for more information on binary trees and their operations!