...

/

Solution Review: Finding Ancestors of a Given Node in a BST

Solution Review: Finding Ancestors of a Given Node in a BST

Learn a detailed analysis of the different ways to solve the “Finding Ancestors of a Given Node in a Binary Search Tree” challenge.

Solution #1: Using a recursive helper function #

Press + to interact
C#
Files
using System;
namespace chapter_6
{
class Solution
{
//Helper Recursive Function to find ancestors of k node
//and add them to the result string
static bool recur(Node rootNode, int k, ref string result)
{
//base cases
if (rootNode == null)
return false;
else if (rootNode.value == k)
return true;
else
{
//To check if target is present in either left or right subtree of currentNode
if (recur(rootNode.leftChild, k, ref result) || recur(rootNode.rightChild, k, ref result))
{
result = result + rootNode.value.ToString() + " ";
return true;
}
}
return false;
}
static string findAncestors(Node rootNode, int k)
{
string result = string.Empty;
recur(rootNode, k, ref result);
return result;
}
static void Main(string[] args)
{
BinarySearchTree BST = new BinarySearchTree(6);
BST.insertBST(1);
BST.insertBST(133);
BST.insertBST(12);
Console.WriteLine(findAncestors(BST.getRoot(), 12));
}
}
}

This solution uses a recursive helper function that starts traversing from the root until the input node and backtracks to append the ancestors that led to the node.

Time complexity

This is the ...

Access this course and 1400+ top-rated courses and projects.