Amazon phone screen - find shortest distance between two nodes in binary tree

The discussion link on Leetcode is here. 

jianminchen

May 18, 2017 2:07 PM

I thought about the algorithm and it should fit in 60 minutes time range, and also need to make the code work, pass a few test cases.

First, write recursive function instead of iterative. Code is simple.

Secondly, recursive is a depth first search algorithm, treat it as a graph search algorithm.

Third, I like to argue that "find lowest common ancestor" maybe is a more complicated algorithm. Better not relate to the algorithm "find lowest common ancestor".

To find a path from root node to search node, the function is designed to find one node a time. The time complexity should be the same to find two nodes one time.

Time complexity is O(n), n is the total nodes of binary tree. Use preorder traversal, visit root first, then visit left and right child.

Here is my C# practice code.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinarySearchTreeTwoNodesDistance
{
    class Program
    {
        internal class Node
        {
            public int Value { get; set; }
            public Node Left { get; set; }
            public Node Right { get; set; }

            public Node(int number)
            {
                Value = number;
            }
        }

        static void Main(string[] args)
        {
            // calculate two nodes distance
            RunTestcase();
        }

        /// <summary>
        /// inorder traversal - 1 2 3 4 5 6 7
        /// </summary>
        public static void RunTestcase()
        {
            var root = new Node(4);
            root.Left = new Node(2);
            root.Left.Left = new Node(1);
            root.Left.Right = new Node(3);
            root.Right = new Node(6);
            root.Right.Left = new Node(5);
            root.Right.Right = new Node(7);

            // distance should be 4 
            var distance = FindDistance(root, root.Left.Right, root.Right.Right);
            Debug.Assert(distance == 4);

            var distance2 = FindDistance(root, root.Left.Right, root.Left.Left);
            Debug.Assert(distance2 == 2); 
        }

        public static int FindDistance(Node root, Node p, Node q)
        {
            IList<Node> possiblePath_1 = new List<Node>();
            IList<Node> possiblePath_2 = new List<Node>();

            IList<Node> searchPath_1 = new List<Node>();
            IList<Node> searchPath_2 = new List<Node>();

            FindPath(root, p, possiblePath_1,ref searchPath_1);
            FindPath(root, q, possiblePath_2,ref searchPath_2);

            if (searchPath_1.Count == 0 || searchPath_2.Count == 0)
            {
                return 0; 
            }

            // find first node not equal 
            int index = 0;
            int length1 = searchPath_1.Count;
            int length2 = searchPath_2.Count;

            while (index < Math.Min(length1, length2) &&
                searchPath_1[index] == searchPath_2[index])
            {
                index++;
            }

            //(length1 - 1) + (length2 - 1) - (2 * (index - 1))
            return length1 + length2 - 2 * index;
        }

        /// <summary>
        /// Do a preorder search for the node
        /// </summary>
        /// <param name="root"></param>
        /// <param name="search"></param>
        /// <param name="possiblePath"></param>
        /// <param name="searchPath"></param>
        public static void FindPath(Node root, Node search, IList<Node> possiblePath, ref IList<Node> searchPath)
        {
            if (root == null || searchPath.Count > 0)
            {
                return;
            }

            if (root == search)
            {
                searchPath = possiblePath;
                searchPath.Add(search);
                return;
            }

            possiblePath.Add(root);
            IList<Node> leftBranch  = new List<Node>(possiblePath);
            IList<Node> rightBranch = new List<Node>(possiblePath);

            FindPath(root.Left, search, leftBranch, ref searchPath);
            FindPath(root.Right, search, rightBranch,ref  searchPath);
        }
    }
}

Actionable Items

July 3, 2019

I should be able to write a few lines of code to solve the problem. I just could not believe that my post has so many issues. It is too time-consuming, and there is elegant solution out there.

There is more simple idea. Use post order to find all nodes on the path from given node p to root node, and save it into hashmap, key is treeNode, value is the distance to given node p; second call using given node q, and then do the same work as given node p, but this time, check all nodes from node q to root to see if it is in hashmap or not, if it is, then lowest common ancestor is found. Add current distance to distance from hashmap. Time complexity: O(N)