...

/

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
main.cs
BST.cs
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 ...