Skip to content

Commit 6aeff63

Browse files
paramagparamag
paramag
authored and
paramag
committed
tree problems
1 parent ea15d21 commit 6aeff63

26 files changed

+814
-57
lines changed

‎Algorithm/.vs/Algorithms/v14/.suo‎

41.5 KB
Binary file not shown.

‎Algorithm/BinaryTree/Algorithms.Problem.BinaryTree.csproj‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,9 +45,12 @@
4545
</ItemGroup>
4646
<ItemGroup>
4747
<Compile Include="ConnectNextNode.cs" />
48+
<Compile Include="DistanceBetweenTwoNodes.cs" />
4849
<Compile Include="LevelSpiralOrder.cs" />
4950
<Compile Include="LowestCommonAncestor.cs" />
51+
<Compile Include="MaxDifferenceForNodeAndAncestor.cs" />
5052
<Compile Include="PathRootToLeaf.cs" />
53+
<Compile Include="PrintCommonPath.cs" />
5154
<Compile Include="Properties\AssemblyInfo.cs" />
5255
<Compile Include="RootToLeafSum.cs" />
5356
<Compile Include="SerializeAndDeserialize.cs" />

‎Algorithm/BinaryTree/ConnectNextNode.cs‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -27,16 +27,16 @@ public void ConnectNode()
2727
// in such cases keep going next until we find the next node.
2828
// For eg1: consider the following tree:
2929
/// 20
30-
/// / \
30+
/// / \
3131
/// 10 30
32-
/// / / \
33-
/// 5 25 35
32+
/// / / \
33+
/// 5 25 35
3434
///
3535
// For eg2: consider the following tree:
3636
/// 20
37-
/// / \
37+
/// / \
3838
/// 10 30
39-
/// / \ \
39+
/// / \ \
4040
/// 5 12 35
4141

4242
// depth wise traversal

‎Algorithm/BinaryTree/DistanceBetweenTwoNodes.cs‎

Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
using DataStructures.Libraries.Trees;
2+
using Microsoft.VisualStudio.TestTools.UnitTesting;
3+
using System;
4+
using System.Collections.Generic;
5+
using System.Linq;
6+
using System.Text;
7+
using System.Threading.Tasks;
8+
9+
namespace Algorithms.Problem.BinaryTree
10+
{
11+
public class BinaryTreeDistance
12+
{
13+
public BinaryTreeNode binaryTreeNode;
14+
public int distance;
15+
16+
public BinaryTreeDistance(BinaryTreeNode binaryTreeNode, int distance)
17+
{
18+
this.binaryTreeNode = binaryTreeNode;
19+
this.distance = distance;
20+
}
21+
}
22+
23+
[TestClass]
24+
public class DistanceBetweenTwoNodes
25+
{
26+
public BinaryTreeNode FindLca(BinaryTreeNode root, BinaryTreeNode node1, BinaryTreeNode node2)
27+
{
28+
if (root == null) return null;
29+
30+
if (root == node1 || root == node2) return root;
31+
32+
BinaryTreeNode left = this.FindLca(root.Left, node1, node2);
33+
BinaryTreeNode right = this.FindLca(root.Right, node1, node2);
34+
35+
if (left != null && right != null)
36+
{
37+
return root;
38+
}
39+
40+
if (left != null) return left;
41+
else return right;
42+
}
43+
44+
public int GetDistanceFromRootUsingRecursion(BinaryTreeNode root, BinaryTreeNode node)
45+
{
46+
int distance = -1;
47+
if (root == null) return -1;
48+
49+
if (root.Value == node.Value) return distance + 1;
50+
51+
distance = this.GetDistanceFromRootUsingRecursion(root.Left, node);
52+
if (distance >= 0) return distance + 1;
53+
54+
distance = this.GetDistanceFromRootUsingRecursion(root.Right, node);
55+
if (distance >= 0) return distance + 1;
56+
57+
return distance;
58+
}
59+
60+
public int GetDistanceFromRoot(BinaryTreeNode root, BinaryTreeNode node)
61+
{
62+
Stack<BinaryTreeDistance> stack = new Stack<BinaryTreeDistance>();
63+
int distance = 0;
64+
stack.Push(new BinaryTreeDistance(root, distance));
65+
66+
while(stack.Count > 0)
67+
{
68+
BinaryTreeDistance distanceNode = stack.Pop();
69+
70+
if (distanceNode.binaryTreeNode.Value == node.Value)
71+
{
72+
return distanceNode.distance;
73+
}
74+
75+
distance = distanceNode.distance + 1;
76+
if (distanceNode.binaryTreeNode.Left != null)
77+
{
78+
stack.Push(new BinaryTreeDistance( distanceNode.binaryTreeNode.Left, distance));
79+
}
80+
81+
if (distanceNode.binaryTreeNode.Right != null)
82+
{
83+
stack.Push(new BinaryTreeDistance(distanceNode.binaryTreeNode.Right, distance));
84+
}
85+
}
86+
87+
return -1;
88+
}
89+
90+
[TestMethod]
91+
public void TestGetDistanceFromRootUsingRecursion()
92+
{
93+
var root = new BinaryTreeNode(1);
94+
95+
root.Left = new BinaryTreeNode(2);
96+
root.Right = new BinaryTreeNode(3);
97+
98+
root.Left.Left = new BinaryTreeNode(4);
99+
root.Left.Right = new BinaryTreeNode(5);
100+
101+
root.Right.Left = new BinaryTreeNode(6);
102+
root.Right.Right = new BinaryTreeNode(7);
103+
104+
BinaryTreeNode node1 = root.Right.Left;
105+
BinaryTreeNode node2 = root.Left.Right;
106+
107+
int distanceNode1 = this.GetDistanceFromRootUsingRecursion(root, node1);
108+
int distanceNode2 = this.GetDistanceFromRootUsingRecursion(root, node2);
109+
}
110+
111+
[TestMethod]
112+
public void TestGetDistanceFromRoot()
113+
{
114+
/// 1
115+
/// / \
116+
/// 2 3
117+
/// / \ / \
118+
/// 4 5 6 7
119+
120+
var root = new BinaryTreeNode(1);
121+
122+
root.Left = new BinaryTreeNode(2);
123+
root.Right = new BinaryTreeNode(3);
124+
125+
root.Left.Left = new BinaryTreeNode(4);
126+
root.Left.Right = new BinaryTreeNode(5);
127+
128+
root.Right.Left = new BinaryTreeNode(6);
129+
root.Right.Right = new BinaryTreeNode(7);
130+
131+
BinaryTreeNode node1 = root.Left.Left;
132+
BinaryTreeNode node2 = root.Left.Right;
133+
134+
int distance1 = this.GetDistanceFromRoot(root, node1);
135+
int distance2 = this.GetDistanceFromRoot(root, node2);
136+
137+
BinaryTreeNode lca = this.FindLca(root, node1, node2);
138+
139+
int lcaDistance = this.GetDistanceFromRoot(root, lca);
140+
141+
int actualDistance = distance1 + distance2 - (2 * lcaDistance);
142+
143+
Assert.AreEqual(2, actualDistance);
144+
}
145+
}
146+
}

‎Algorithm/BinaryTree/LevelSpiralOrder.cs‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -22,9 +22,9 @@ public LevelSpiralOrder(BinaryTreeNode root)
2222
this.Root = root;
2323
}
2424

25-
public int[] PrintSpiralOrder()
25+
public double[] PrintSpiralOrder()
2626
{
27-
List<int> spiralOrderArray = new List<int>();
27+
List<double> spiralOrderArray = new List<double>();
2828

2929
// 1. Use two stacks S1 and S2
3030
// 2. Push first item to Stack S1
@@ -92,7 +92,7 @@ public void ValidateTreeSpiralOrder()
9292

9393
var spiralOrder = new LevelSpiralOrder(binarySearchTree.Root);
9494

95-
int[] spiralOrderActual = spiralOrder.PrintSpiralOrder();
95+
double[] spiralOrderActual = spiralOrder.PrintSpiralOrder();
9696

9797
for(int i=0; i < spiralOrderExpected.Length; i++)
9898
{

‎Algorithm/BinaryTree/LowestCommonAncestor.cs‎

Lines changed: 68 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,8 +55,75 @@ public BinaryTreeNode FindLowestCommonAncestor(BinaryTreeNode root, BinaryTreeNo
5555
return leftNode != null ? leftNode : rightNode;
5656
}
5757

58+
public BinaryTreeNode FindLcaUsingParentPointer(BinaryTreeNode root, BinaryTreeNode node1, BinaryTreeNode node2)
59+
{
60+
BinaryTreeNode lca = null;
61+
62+
// build hashtable using parent node.
63+
Dictionary<double, double> childParent = new Dictionary<double, double>();
64+
65+
// take node1 to build the has map.
66+
while(node1 != null && node1.Parent != null)
67+
{
68+
childParent.Add(node1.Value, node1.Parent.Value);
69+
node1 = node1.Parent;
70+
}
71+
72+
// add the root and it's parent to null
73+
childParent.Add(node1.Value, -1);
74+
75+
while(node2 != null)
76+
{
77+
if (childParent.ContainsKey(node2.Value))
78+
{
79+
lca = node2;
80+
81+
// break and this is the lowest ancestor.
82+
break;
83+
}
84+
85+
node2 = node2.Parent;
86+
}
87+
88+
return lca;
89+
}
90+
91+
[TestMethod]
92+
public void ValidateLCAUsingParentPointer()
93+
{
94+
BinaryTreeNode root = new BinaryTreeNode(20);
95+
root.Left = new BinaryTreeNode(8);
96+
root.Right = new BinaryTreeNode(22);
97+
98+
root.Left.Parent = root;
99+
root.Right.Parent = root;
100+
101+
root.Left.Left = new BinaryTreeNode(4);
102+
root.Left.Right = new BinaryTreeNode(12);
103+
104+
root.Left.Left.Parent = root.Left;
105+
root.Left.Right.Parent = root.Left;
106+
107+
root.Left.Right.Left = new BinaryTreeNode(10);
108+
root.Left.Right.Right = new BinaryTreeNode(14);
109+
110+
root.Left.Right.Left.Parent = root.Left.Right;
111+
root.Left.Right.Right.Parent = root.Left.Right;
112+
113+
BinaryTreeNode node1 = root.Left.Right.Left;
114+
BinaryTreeNode node2 = root.Left.Right.Right;
115+
116+
BinaryTreeNode lca = this.FindLcaUsingParentPointer(root, node1, node2);
117+
Assert.AreEqual(lca.Value, 12);
118+
119+
node1 = root.Left;
120+
node2 = root.Left.Right.Right;
121+
lca = this.FindLcaUsingParentPointer(root, node1, node2);
122+
Assert.AreEqual(lca.Value, 8);
123+
}
124+
58125
[TestMethod]
59-
public void ValidateTreeSpiralOrder()
126+
public void ValidateLCA()
60127
{
61128
var binarySearchTree = new BinarySearchTree();
62129
binarySearchTree.PopulateDefaultBalanceTree();

‎Algorithm/BinaryTree/MaxDifferenceForNodeAndAncestor.cs‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
using DataStructures.Libraries.Trees;
2+
using Microsoft.VisualStudio.TestTools.UnitTesting;
3+
using System;
4+
using System.Collections.Generic;
5+
using System.Linq;
6+
using System.Text;
7+
using System.Threading.Tasks;
8+
9+
namespace Algorithms.Problem.BinaryTree
10+
{
11+
/// <summary>
12+
/// INCOMPLETE!!!!!!!!!!!!!!!
13+
/// </summary>
14+
[TestClass]
15+
public class MaxDifferenceForNodeAndAncestor
16+
{
17+
public void MaxDiffBetweenNodeAndAncestor(BinaryTreeNode root)
18+
{
19+
20+
}
21+
22+
public double GetMinFromSubTree(BinaryTreeNode node, double minValue)
23+
{
24+
if (node == null) return minValue;
25+
26+
minValue = Math.Min(node.Value, minValue);
27+
28+
minValue = this.GetMinFromSubTree(node.Left, minValue);
29+
minValue = this.GetMinFromSubTree(node.Right, minValue);
30+
31+
return minValue;
32+
}
33+
34+
[TestMethod]
35+
public void TestIsBinaryTreeABST()
36+
{
37+
BinaryTreeNode root = new BinaryTreeNode(8);
38+
root.Left = new BinaryTreeNode(3);
39+
root.Right = new BinaryTreeNode(10);
40+
41+
root.Left.Left = new BinaryTreeNode(1);
42+
root.Left.Right = new BinaryTreeNode(6);
43+
44+
root.Right.Right = new BinaryTreeNode(14);
45+
46+
root.Left.Right.Left = new BinaryTreeNode(4);
47+
root.Left.Right.Right = new BinaryTreeNode(7);
48+
49+
root.Right.Right.Left = new BinaryTreeNode(13);
50+
51+
double result = this.GetMinFromSubTree(root.Left, double.MaxValue);
52+
}
53+
}
54+
}

0 commit comments

Comments
 (0)