C# Coding Test Course, Finding the Parent of a Tree

Problem Description

The goal of this problem is to find the parent node of a specific node in a given binary tree.
A binary tree is a hierarchical data structure in which each node can have up to two children.
Our objective is to write a program that correctly finds the parent of the node based on the input node.

Problem Input

    The tree is given as an array, with each element representing a node of the tree. 
    The index of the array represents the position of the node, and index 0 is the root node. 
    For example, in the array [3, 5, 1, 6, 2, 0, 8],
    3 is the root node,
    5 is the left child of node 3,
    1 is the right child of node 3,
    6 is the left child of node 5, 
    2 is the right child of node 5,
    0 is the left child of node 1,
    8 is the right child of node 1.

Problem Output

    Outputs the value of the parent node for a specific node. 
    If there is no parent node, output -1.

Examples

Input

    Tree: [3, 5, 1, 6, 2, 0, 8]
    Node: 6

Output

    5

Input

    Tree: [3, 5, 1, 6, 2, 0, 8]
    Node: 3

Output

    -1

Solution Approach

To solve this problem, it is necessary to understand the structure of the tree and how to find the parent of each node.
In a binary tree, the parent node of each node can be found using the index of the child node and mathematical operations.

Finding the Parent Node

The index of the parent node for a given index can be calculated as follows:

  • Parent node index: parentIndex = (childIndex - 1) / 2

– Here, childIndex is the index of the node you want to find.
– If childIndex is 0, this is the root node, so there is no parent node.

Implementation

Now, let’s write the C# code based on the above approach.


public class TreeNodeSearcher 
{
    public static int FindParent(int[] tree, int childIndex) 
    {
        // Check if the input childIndex is valid
        if (childIndex < 0 || childIndex >= tree.Length) 
        {
            throw new ArgumentOutOfRangeException("Child index is out of the range of the tree array.");
        }
        
        // No parent for the root node
        if (childIndex == 0) 
        {
            return -1; // No parent
        }

        // Calculate parent index
        int parentIndex = (childIndex - 1) / 2;
        return tree[parentIndex];
    }
}

Tests

To effectively test the above method, let’s create some cases.


public class Program 
{
    public static void Main() 
    {
        int[] tree = {3, 5, 1, 6, 2, 0, 8};

        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 3)); // Output: 5
        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 0)); // Output: -1
        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 5)); // Output: 1
        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 1)); // Output: 3
    }
}

Conclusion

We have successfully implemented an algorithm to find the parent node of a specific node in a given binary tree.
This algorithm is very efficient with a time complexity of O(1).
Understanding and utilizing the structure of the tree is important, and these fundamental concepts can be applied usefully when dealing with more complex data structures.

Additional Learning

To deepen your understanding of trees, it is recommended to explore advanced topics such as binary search trees, AVL trees, and heaps.
These data structures will be very helpful in solving a variety of algorithm problems.