CareerCup

class Node
{
	public Node left { get; set; }
	public Node right { get; set; }
}

int GetHeightDifference(Node root, Node node1, Node node2) {
	return Math.Abs(GetHeight(root, node1, 0) - GetHeight(root, node2, 0));
}

///Return -1 if node wasn't found in tree
int GetHeight(Node root, Node node, int depth) {
	if (root == null || node == null)
		return -1;
		
	if (root==node)
		return depth;
	
	return Math.Max(GetHeight(root.left, node, depth+1),GetHeight(root.right, node, depth+1));

}

#include <bits/stdc++.h>

using namespace std ;

vector<int> vec[1001] ;
int par[1001] ;
int lev[1001] ;
bool visit[1001];

void dfs(int x)
{
  stack<int> sp ;

  sp.push(x) ;

  while(!sp.empty())
  {
    int f = sp.top() ;

    if(!visit[f])
        visit[f] = true ;

      sp.pop() ;

      int sz = vec[f].size() ;

      for(int i = 0 ; i < sz ; i++)
      {
        int c = vec[f][i] ;

        if(!visit[c])
        {
          lev[c] = lev[par[c]] + 1 ;
          sp.push(c) ;
        }
      }
  }
}

int main()
{
  int N ;

  cin >> N ;

  for(int i = 1 ; i <= N - 1 ; i++)
  {
    int u , v ;

    cin >> u >> v ;

    par[v] = u ;

    vec[u].push_back(v) ;
    vec[v].push_back(u) ;
  }
  lev[1] = 0 ;

  dfs(1) ;

/*  7
1 2
1 5
2 3
3 7
5 4 */

// difference between any node can now be found by simply subtracting the lev[u] - lev[v]


  return 0 ;
}

#include <bits/stdc++.h>

using namespace std ;

vector<int> vec[1001] ;
int par[1001] ;
int lev[1001] ;
bool visit[1001];

void dfs(int x)
{
  stack<int> sp ;

  sp.push(x) ;

  while(!sp.empty())
  {
    int f = sp.top() ;

    if(!visit[f])
        visit[f] = true ;

      sp.pop() ;

      int sz = vec[f].size() ;

      for(int i = 0 ; i < sz ; i++)
      {
        int c = vec[f][i] ;

        if(!visit[c])
        {
          lev[c] = lev[par[c]] + 1 ;
          sp.push(c) ;
        }
      }
  }
}

int main()
{
  int N ;

  cin >> N ;

  for(int i = 1 ; i <= N - 1 ; i++)
  {
    int u , v ;

    cin >> u >> v ;

    par[v] = u ;

    vec[u].push_back(v) ;
    vec[v].push_back(u) ;
  }
  lev[1] = 0 ;

  dfs(1) ;

/*  7
1 2
1 5
2 3
3 7
5 4 */

// difference between any node can now be found by simply subtracting the lev[u] - lev[v]


  return 0 ;
}

struct TreeNode {
	int value;
	struct TreeNode* left;
	struct TreeNode* right;
};

void traversalTree(TreeNode* root, TreeNode* node1, TreeNode* node2, int& h1, int& h2)
{
	queue<TreeNode*> travQueue;
	int levelheight = 1;
	int numNodes = 1;
	int hNode1 = 0, hNode2 = 0;
	TreeNode* curNode = nullptr;

	if (root == NULL || node1 == NULL || node2 == NULL)
		return;

	travQueue.emplace(root);
	while (!travQueue.empty())
	{
		curNode = travQueue.front();
		travQueue.pop();
		numNodes--;
		if (curNode == node1) hNode1 = levelheight;
		if (curNode == node2) hNode2 = levelheight;
		if (hNode1 != 0 && hNode2 != 0)
			break;

		if (curNode->left)
			travQueue.emplace(curNode->left);
		if (curNode->right)
			travQueue.emplace(curNode->right);
		if (numNodes == 0)
		{
			levelheight++;
			numNodes = travQueue.size();
		}
	}

	h1 = hNode1;
	h2 = hNode2;
}

void findNodesHeightDifference(TreeNode* root, TreeNode* node1, TreeNode* node2, int& diff)
{
	int h1=0, h2=0;
	traversalTree(root, node1, node2, h1, h2);

	if (h1!=0 && h2 != 0)
		diff = abs(h1-h2);
	else
		diff = 0;
}

find the level for both nodes and return the abs difference of them

def height_diff(root, n1, n2, l, height):
    if root:
        if root.key == n1 or root.key == n2:
            height.append(l)
        height_diff(root.left, n1, n2, l + 1, height)
        height_diff(root.right, n1, n2, l + 1, height)


def get_height_diff(root, n1, n2):
    height = []
    height_diff(root, n1, n2, 0, height)
    return abs(height[0] - height[1])