[go: up one dir, main page]
Scribd
Upload
42 views2 pages

Mytreenode: Find The Distance Between Two Nodes in Binary Tree: Class

The document describes how to find the distance between two nodes in a binary tree. It defines a MyTreeNode class to represent nodes, with data, left, and right child properties. The Distance method finds the lowest common ancestor (LCA) of the two nodes using the FindLCA method, and calculates each node's level from the root using FindLevel. It then returns the distance between the nodes as the sum of their levels from the LCA minus twice the LCA's level.

Uploaded by

Anonymous y4akHM3WM
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
42 views2 pages

Mytreenode: Find The Distance Between Two Nodes in Binary Tree: Class

The document describes how to find the distance between two nodes in a binary tree. It defines a MyTreeNode class to represent nodes, with data, left, and right child properties. The Distance method finds the lowest common ancestor (LCA) of the two nodes using the FindLCA method, and calculates each node's level from the root using FindLevel. It then returns the distance between the nodes as the sum of their levels from the LCA minus twice the LCA's level.

Uploaded by

Anonymous y4akHM3WM
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Find the distance between two nodes in binary tree:

class MyTreeNode
{
public int Data { get; set; }
public MyTreeNode Left { get; set; }
public MyTreeNode Right { get; set; }
public MyTreeNode(int data)
{
this.Data = data;
}
}

class QTwoNodeDis
{
public static int Distance(MyTreeNode root, MyTreeNode node1, MyTreeNode node2)
{
var node = FindLCA(root, node1, node2);
int distLCA = FindLevel(root, node);
int dist1 = FindLevel(root, node1);
int dist2 = FindLevel(root, node2);

return dist1 + dist2 - 2 * distLCA;


}

private static MyTreeNode FindLCA(MyTreeNode root, MyTreeNode node1, MyTreeNode node2)


{
if (root == null) return null;
//
if (root.Data == node1.Data || root.Data== node2.Data)
return root;
//

MyTreeNode left_lca = FindLCA(root.Left, node1, node2);


MyTreeNode right_lca = FindLCA(root.Right, node1, node2);

if (left_lca != null && right_lca != null)


//LCA
return root;
return left_lca != null ? left_lca : right_lca;
}

private static int FindLevel(MyTreeNode root, MyTreeNode node)


{
if (root == null)
return -1;
if(root.Data == node.Data)
return 0;

int level = FindLevel(root.Left, node);

if (level == -1)
level = FindLevel(root.Right, node);
if(level != -1)
return level + 1;

return -1;
}
}

You might also like