Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 776 - binary search tree split tree by target value
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BinarySearchTreeSplitTree
{
/// <summary>
/// The algorith is written for my mock interview to test the candidate recursive solution.
/// Leetcode 776: Split binary search tree
/// </summary>
class Program
{
internal class TreeNode
{
public int Value { get; set; }
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
public TreeNode(int number)
{
Value = number;
}
}
static void Main(string[] args)
{
RunTestcase();
}
public static void RunTestcase()
{
// work on root node
var node20 = new TreeNode(20);
// work on level 1
var node9 = new TreeNode(9);
var node25 = new TreeNode(25);
// work on connection from root node to its children
node20.Left = node9;
node20.Right = node25;
// work on level 2
var node5 = new TreeNode(5);
var node12 = new TreeNode(12);
// work on connection from level 1's nodes to their children
node9.Left = node5;
node9.Right = node12;
// work on level 3
var node11 = new TreeNode(11);
var node14 = new TreeNode(14);
// work on connection from level 2's nodes to their children
node12.Left = node11;
node12.Right = node14;
var successor1 = SplitTree(node20, 15);
var successor2 = SplitTree(node20, 9);
var successor3 = SplitTree(node20, 11);
}
/// <summary>
/// Split binary search tree
/// First tree with node value small and equal to the target value.
/// Second tree with node value greater than the target value.
/// </summary>
/// <param name="root"></param>
/// <param name="givenNode"></param>
/// <returns></returns>
public static TreeNode[] SplitTree(TreeNode root, int target)
{
if (root == null)
{
return new TreeNode[2];
}
var splitLeftSubTree = root.Value > target;
if (splitLeftSubTree)
{
var childTrees = SplitTree(root.Left, target);
var tmp = childTrees[1];
childTrees[1] = root;
childTrees[1].Left = tmp;
return childTrees;
}
else
{
var childTrees = SplitTree(root.Right, target);
var tmp = childTrees[0];
childTrees[0] = root;
childTrees[0].Right = tmp;
return childTrees;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment