Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
the longest path will be from a leave to an other leave or from a leave to the root. So, all inner nodes, except the root are not the end points.
One way to find it, is to go from each leave upwards, storing the max. distance to a leave for each subtree and maximize left+right+1 at each node. This takes O(n) time and O(n) space.
Do a post order traversal of the tree calculating the length of increasing and decreasing sequence for the left and right child
class Node{
int data;
Node left, right;
public Node(int x){
data=x;
left=right=null;
}
}
class Result{
int inc,dec;
}
public class LCSInBT {
public static int max;
public static void main(String[] args) {
Node n=new Node(6);
n.left=new Node(5);
n.left.left=new Node(3);
n.left.right=new Node(4);
n.left.left.left=new Node(2);
n.right=new Node(7);
n.right.left=new Node(8);
n.right.left.right=new Node(9);
lcs(n);
System.out.println(max);
}
private static Result lcs(Node n) {
Result res=new Result();
if(n==null){
res.dec=0; res.inc=0;
return res;
}
res.dec=1; res.inc=1;
Result l=lcs(n.left);
Result r=lcs(n.right);
if(n.left!=null){
if(n.left.data+1==n.data){
res.inc+=l.inc;
}
if(n.data+1==n.left.data){
res.dec+=l.dec;
}
}
if(n.right!=null){
if(n.right.data+1==n.data){
res.inc=Math.max(res.inc,r.inc+1);
}
if(n.right.data==n.data+1){
res.dec=Math.max(res.dec,r.dec+1);
}
}
max=Math.max(findLen(n,l,r), max);
return res;
}
private static int findLen(Node n, Result l, Result r) {
int len=0;
if(n.left!=null && n.right!=null){
if(n.data+1==n.left.data && n.data==n.right.data+1){
len=l.dec+r.inc+1;
}
else if(n.data==n.left.data+1 && n.data+1==n.right.data){
len=l.inc+r.dec+1;
}
else if(n.data+1==n.left.data){
len=1+l.dec;
}
else if(n.data==n.left.data+1){
len=1+l.inc;
}
else if(n.data+1==n.right.data){
len=1+r.dec;
}
else if(n.data==n.right.data+1){
len=1+r.inc;
}
}
return len;
}
}
Postorder traversal of the tree calculating the length of increasing and decreasing sequence for both left and right child
class Node{
int data;
Node left, right;
public Node(int x){
data=x;
left=right=null;
}
}
class Result{
int inc,dec;
}
public class LCSInBT {
public static int max;
public static void main(String[] args) {
Node n=new Node(6);
n.left=new Node(5);
n.left.left=new Node(3);
n.left.right=new Node(4);
n.left.left.left=new Node(2);
n.right=new Node(7);
n.right.left=new Node(8);
n.right.left.right=new Node(9);
lcs(n);
System.out.println(max);
}
private static Result lcs(Node n) {
Result res=new Result();
if(n==null){
res.dec=0; res.inc=0;
return res;
}
res.dec=1; res.inc=1;
Result l=lcs(n.left);
Result r=lcs(n.right);
if(n.left!=null){
if(n.left.data+1==n.data){
res.inc+=l.inc;
}
if(n.data+1==n.left.data){
res.dec+=l.dec;
}
}
if(n.right!=null){
if(n.right.data+1==n.data){
res.inc=Math.max(res.inc,r.inc+1);
}
if(n.right.data==n.data+1){
res.dec=Math.max(res.dec,r.dec+1);
}
}
max=Math.max(findLen(n,l,r), max);
return res;
}
private static int findLen(Node n, Result l, Result r) {
int len=0;
if(n.left!=null && n.right!=null){
if(n.data+1==n.left.data && n.data==n.right.data+1){
len=l.dec+r.inc+1;
}
else if(n.data==n.left.data+1 && n.data+1==n.right.data){
len=l.inc+r.dec+1;
}
else if(n.data+1==n.left.data){
len=1+l.dec;
}
else if(n.data==n.left.data+1){
len=1+l.inc;
}
else if(n.data+1==n.right.data){
len=1+r.dec;
}
else if(n.data==n.right.data+1){
len=1+r.inc;
}
}
return len;
}
}
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
class LongestPathFinder:
def check_if_longest(self, key, l_path, r_path):
if len(l_path) + len(r_path) + 1 > self.longest_path_len:
self.longest_path_len = len(l_path) + len(r_path) + 1
self.longest_path_root = key
self.left_deepest_path = l_path
self.right_deepest_path = r_path
def find_deepest_path(self,node):
if node == None:
return []
left_deepest_path = self.find_deepest_path(node.left)
right_deepest_path = self.find_deepest_path(node.right)
self.check_if_longest(node.key, left_deepest_path, right_deepest_path)
if len(left_deepest_path) >= len(right_deepest_path):
return left_deepest_path + [node.key]
else:
return right_deepest_path + [node.key]
def __init__(self,root):
self.longest_path_root = None
self.left_deepest_path = []
self.right_deepest_path = []
self.longest_path_len = 0
self.find_deepest_path(root)
if self.longest_path_len == 0:
self.longest_path = []
else:
self.longest_path = self.left_deepest_path + \
[self.longest_path_root] + \
list(reversed(self.right_deepest_path))
The longest path has to be rooted in one node and it is the concatenation of the longest path on the left, the node, and the longest path on the right. For each node, find the longest path rooted on it and find the max of all.
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
class LongestPathFinder:
def check_if_longest(self, key, l_path, r_path):
if len(l_path) + len(r_path) + 1 > self.longest_path_len:
self.longest_path_len = len(l_path) + len(r_path) + 1
self.longest_path_root = key
self.left_deepest_path = l_path
self.right_deepest_path = r_path
def find_deepest_path(self,node):
if node == None:
return []
left_deepest_path = self.find_deepest_path(node.left)
right_deepest_path = self.find_deepest_path(node.right)
self.check_if_longest(node.key, left_deepest_path, right_deepest_path)
if len(left_deepest_path) >= len(right_deepest_path):
return left_deepest_path + [node.key]
else:
return right_deepest_path + [node.key]
def __init__(self,root):
self.longest_path_root = None
self.left_deepest_path = []
self.right_deepest_path = []
self.longest_path_len = 0
self.find_deepest_path(root)
if self.longest_path_len == 0:
self.longest_path = []
else:
self.longest_path = self.left_deepest_path + \
[self.longest_path_root] + \
list(reversed(self.right_deepest_path))
import java.util.*;
import java.lang.Math;
public class BTLongestConsecutivePath {
public static void main(String[] args) {
BT t = new BT();
t.add(6);
t.add(2);
t.add(1);
t.add(0);
t.add(3);
t.add(4);
t.add(5);
t.postorder();
System.out.println(t.searchLongestPath());
}
public static class BT {
Node root;
ArrayList<Integer> array;
public BT() {
this.root = null;
this.array = new ArrayList<Integer>();
}
public void add(int val) {
root = add(root, val);
}
public Node add(Node root, int val) {
if(root == null) return new Node(val, null, null);
else {
if(root.val < val) {
root.right = add(root.right, val);
return root;
} else if(root.val > val) {
root.left = add(root.left, val);
return root;
} else {
return root;
}
}
}
public void inorder() { inorder(root); }
public void inorder(Node root) {
if(root != null) {
inorder(root.left);
System.out.println(root.val);
inorder(root.right);
}
}
public void postorder() { postorder(root); }
public void postorder(Node root) {
if(root != null) {
postorder(root.left);
postorder(root.right);
array.add(root.val);
System.out.println(root.val);
}
}
public ArrayList<String> searchConsecutive() {
ArrayList<String> consecutive = new ArrayList<String>();
String str = "";
for(int i = 0; i < array.size()-1; i++) {
if(Math.abs(array.get(i)-array.get(i+1)) == 1) {
if(str.length() == 0) {
str += array.get(i)+","+array.get(i+1)+",";
} else {
str += array.get(i+1)+",";
}
} else {
if(str.length() != 0) consecutive.add(str);
str = "";
}
}
return consecutive;
}
public String searchLongestPath() {
ArrayList<String> consecutive = searchConsecutive();
int original_size = consecutive.size();
for(int i = 0; i < original_size; i++) {
for(int j = 0; j < original_size; j++) {
if(i != j) {
String str1 = consecutive.get(i);
String str2 = consecutive.get(j);
if(Math.abs(str1.charAt(str1.length()-2)-str2.charAt(str2.length()-2)) == 1) {
for(int x = str2.length()-2; x >= 0; x-=2) {
str1 += str2.charAt(x)+",";
}
consecutive.add(str1);
}
}
}
}
int length = 0;
int index = -1;
for(int i = 0; i < consecutive.size(); i++) {
if(consecutive.get(i).length() > length) {
length = consecutive.get(i).length();
index = i;
}
}
return index == -1 ? "" : consecutive.get(index);
}
}
public static class Node {
Node left, right;
int val;
public Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
public class LongestPathInBinaryTree {
private static class Node {
Node left;
Node right;
int payload;
public String toString() { return ""+payload; }
}
public static void main(String[] args) {
Node n7 = new Node(); n7.payload = 7;
Node n6 = new Node(); n6.payload = 6;
Node n4 = new Node(); n4.payload = 4;
Node n5 = new Node(); n5.payload = 5; n5.left = n6; n5.right = n7;
Node n2 = new Node(); n2.payload = 2; n2.left = n4; n2.right = n5;
Node n3 = new Node(); n3.payload = 3;
Node n1 = new Node(); n1.payload = 1; n1.left = n2; n1.right = n3;
System.out.println(getLongestPath(n1, 0));
}
private static LinkedList<Node> getLongestPath(Node root, int level) {
LinkedList<Node> result = new LinkedList<Node>();
LinkedList<Node> leftPath = null;
if (root.left != null) leftPath = getLongestPath(root.left, 1);
LinkedList<Node> rightPath = null;
if (root.right != null) rightPath = getLongestPath(root.right, 1);
if (level > 0) {
List<Node> childPath = compare(leftPath, rightPath);
if (childPath != null) result.addAll(childPath);
result.add(root);
}
else {
if (leftPath != null) result.addAll(leftPath);
result.add(root);
if (rightPath != null) {
for (Iterator<Node> it = rightPath.descendingIterator(); it.hasNext();) {
result.add(it.next());
}
}
}
return result;
}
private static List<Node> compare(List<Node> l , List<Node> r) {
if (l == null && r == null) return null;
if (l == null) return r;
if (r == null) return l;
return r.size() >= l.size()? r: l;
}
}
- Generate child-to-parent consecutive depth map for each node
* Find the longest ascending sequence if its left child < itself
* Find the longest descending sequence if its left child > itself
* Find the longest ascending sequence of its right child < itself
* Find the longest descending sequence if its right child > itself
* 0 sequence if any child is null
* 0 sequence if any child is equal to itself
- Find the node with longest consecutive node in above map
* Take the longer sequence if both children has same order sequence
* Sum the sequence if two children has difference order sequence
Details: //cpluspluslearning-petert.blogspot.co.uk/2017/01/bts-find-longest-consecutive-path_13.html
Test
void TestFindTheLongestOrderedSeq()
{
std::vector<double> input = { 1.0, 2.0, 3.0, 4.0, 5.0 };
TreeNode<double> *root = NULL;
// 3
// 1 4
// 2 5
root = ConstructTreeOnSortedValueBFS(input);
auto path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0 });
input = { 6.0, 7.0, 8.0, 9.0 };
TreeNode<double> *subTree1 = ConstructTreeOnSortedValueDFS(input);
input = { 10.0, 11.0, 12.0, 13.0 , 14.0 };
TreeNode<double> *subTree2 = ConstructTreeRecursive(input);
input = { 15.0, 16.0, 17.0, 18.0 };
TreeNode<double> *subTree3 = ConstructTreeOnSortedValueDFS(input);
input = { 19.0, 20.0, 21.0, 22.0 , 23.0 };
TreeNode<double> *subTree4 = ConstructTreeRecursive(input);
TreeNode<double> *leftestNode = FindLeftestNode(root);
assert(leftestNode != NULL);
leftestNode->left = subTree1;
// 3
// 1 4
// 8 2 5
// 6 9
// 7
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0 });
TreeNode<double> *rightestNode = FindRightestNode(root);
assert(rightestNode != NULL);
rightestNode->left = subTree2;
// 3
// 1 4
// 8 2 5
// 6 9 12
// 7 10 13
// 11 14
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
TreeNode<double> *firstLeftRighestNode = FindRightestNode(root->left);
assert(firstLeftRighestNode != NULL);
firstLeftRighestNode->right = subTree3;
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
TreeNode<double> *firstRightLeftestNodeOfS2 = FindRightestNode(subTree2->left);
assert(firstRightLeftestNodeOfS2 != NULL);
firstRightLeftestNodeOfS2->left = subTree4;
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
// 21
// 19 22
// 20 23
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
TreeNode<double> *rightestNodeOfS2 = FindRightestNode(subTree2);
assert(rightestNodeOfS2 != NULL);
for (size_t i = 0; i < 8; ++i) {
rightestNodeOfS2->right = new TreeNode<double>(100.0 + i);
rightestNodeOfS2 = rightestNodeOfS2->right;
}
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
// 21 100
// 19 22 101
// 20 23 102
// 103
// 104
// 105
// 106
// 107
// clean up
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0, 100.0,
101.0, 102.0, 103.0, 104.0, 105.0, 106.0, 107.0});
// clean up
DeleteTree_TD(&root);
}
private static List<TreeNode> longestPath0(TreeNode node, List<TreeNode> longestPath, boolean descending) {
if (node == null)
return new ArrayList<>(longestPath);
//we are asked to include a path that is already passed
if (longestPath.size() > 0) {
if ((descending && lastElement(longestPath).getValue() - 1 == node.getValue()) ||
(!descending && lastElement(longestPath).getValue() + 1 == node.getValue())
) {
ArrayList<TreeNode> list = new ArrayList<>();
list.addAll(longestPath);
list.add(node);
List<TreeNode> leftLongest = longestPath0(node.getLeft(), list, descending);
List<TreeNode> rightLongest = longestPath0(node.getRight(), list, descending);
return leftLongest.size() > rightLongest.size() ? leftLongest : rightLongest;
} else {
return longestPath;
}
} else {
List<List<TreeNode>> resultsHolder = new ArrayList<>();
List<TreeNode> leftDesc = longestPath0(node.getLeft(), Collections.emptyList(), descending);
List<TreeNode> leftAsc = longestPath0(node.getLeft(), Collections.emptyList(), !descending);
List<TreeNode> rightDesc = longestPath0(node.getRight(), Collections.emptyList(), descending);
List<TreeNode> rightAsc = longestPath0(node.getRight(), Collections.emptyList(), !descending);
List<TreeNode> leftDescNodeIncluded = longestPath0(node.getLeft(), Collections.singletonList(node), descending);
List<TreeNode> leftAscNodeIncluded = longestPath0(node.getLeft(), Collections.singletonList(node), !descending);
List<TreeNode> rightDescNodeIncluded = longestPath0(node.getRight(), Collections.singletonList(node), descending);
List<TreeNode> rightAscNodeIncluded = longestPath0(node.getRight(), Collections.singletonList(node), !descending);
resultsHolder.add(leftAsc);
resultsHolder.add(leftDesc);
resultsHolder.add(rightAsc);
resultsHolder.add(rightDesc);
resultsHolder.add(leftDescNodeIncluded);
resultsHolder.add(leftAscNodeIncluded);
resultsHolder.add(rightDescNodeIncluded);
resultsHolder.add(rightAscNodeIncluded);
resultsHolder.add(join(leftAscNodeIncluded, rightDescNodeIncluded));
resultsHolder.add(join(leftDescNodeIncluded, rightAscNodeIncluded));
return resultsHolder.stream().max((o1, o2) -> Integer.compare(o1.size(), o2.size())).get();
}
}
private static List<TreeNode> join(List<TreeNode> left, List<TreeNode> right) {
ArrayList<TreeNode> result = new ArrayList<>();
for (int i = left.size() - 1; i > 0; i--) {
result.add(left.get(i));
}
result.addAll(right);
return result;
}
private static TreeNode lastElement(List<TreeNode> longestPath) {
return longestPath.get(longestPath.size() - 1);
}
private static List<TreeNode> longestPath(@NonNull final TreeNode node) {
return longestPath0(node, Collections.emptyList(), false);
}
The longest path has to be rooted in one node and it is the concatenation of the longest path on the left, the node, and the longest path on the right. For each node, find the longest path rooted on it and find the max of all.
- Terio December 11, 2016