Amazon Interview Question Backend Developers
Country: United States
What I tried is to first calculate the height of the binary tree. Then store the nodes in an array and print when the height is equal to the array length. I know this is not a good approach. Hence I am here.
Here is my working code:
package com.company;
class Node{
Node left;
Node right;
int data;
Node(int data){
this.left = null;
this.right = null;
this.data = data;
}
}
public class Main {
public static void main(String[] args) {
// write your code here
int arr[] = new int[10];
int counter=0;
Node node = new Node(5);
node.left = new Node(2);
node.left.left = new Node(1);
node.left.left.left = new Node(7);
node.left.left.right = new Node(8);
node.left.right = new Node(3);
node.left.right.left = new Node(9);
node.right = new Node(6);
node.right.left = new Node(11);
node.right.left.left = new Node(15);
node.right.left.left.right = new Node(10);
node.right.right = new Node(12);
int h = height(node);
printLongestPath(node, arr, counter, h);
}
private static void printLongestPath(Node node, int arr[], int counter, int h){
if(node==null) {
return;
}
arr[counter++] = node.data;
if(node.left == null && node.right == null){
printArray(arr,counter, h);
}
printLongestPath(node.left, arr, counter, h);
printLongestPath(node.right, arr, counter, h);
}
private static void printArray(int arr[], int counter, int h){
if(counter==h) {
for (int i = 0; i < counter; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
private static int height(Node node){
if(node==null)
return 0;
if(node.left == null && node.right == null) {
return 1;
}
else {
return 1 + Math.max(height(node.left), height(node.right));
}
}
}
It's clearer if you move the check if(counter==h) out of the method like:
if(node.left == null
&& node.right == null
&& counter==h)
{
printArray(arr,counter, h);
return; // since left and right are null
}
This approach requires two passes of the tree. If you use extra space to keep discovered paths in memory, you could do it with just one pass of the tree.
var longestPath = function (root) {
var longestPathHelper = function (root) {
if(root == null) return ;
arr.push(root.val);
if (checkHeight(root.left) > checkHeight(root.right)) {
longestPathHelper(root.left);
}
else {
longestPathHelper(root.right);
}
}
var arr = [];
longestPathHelper(root);
return arr;
}
var checkHeight = function (root) {
if (root == null) return 0;
return 1 + Math.max(checkHeight(root.left), checkHeight(root.right));
}
I think encoding the path traversal while finding the max height can be useful information.
pair<int, string> longestPath(Node* node) {
if(!node) return make_pair(0, "");
auto L = longestPath(node->left);
auto R = longestPath(node->right);
if(L.first < R.first) return make_pair(R.first + 1, "R" + R.second);
else return make_pair(L.first + 1, "L" + L.second);
}
void printLongestPath(Node* node){
auto P = longestPath(node);
Node* n = node;
for(int i = 0; i < P.second.length(); i++) {
cout << n->val <<" ";
if(P.second[i] == 'L') n = n->left;
else n = n->right;
}
}
function traverse (node, path, length) {
if (!node) {
return {
path: path,
length: length
}
}
var l = traverse(node.left, path, length)
var r = traverse(node.right, path, length)
var o = {}
if (l.length >= r.length) {
path = l.path
length = l.length
direction = ' L'
} else {
path = r.path
length = r.length
direction = ' R'
}
o.length = ++length
o.path = (path.length ? direction + '->' : '') + path
o.path = node.value + o.path
return o
}
module.exports = function (root) {
var path = ''
var length = 0
return traverse(root, path, length)
}
var c = {}
c.value = 3
c.right = c.left = null
var b = {}
b.value = 7
b.right = b.left = null
var a = {}
a.value = 2
a.left = null
a.right = c
var root = {}
root.value = 4
root.left = a
root.right = b
var longest = module.exports(root)
console.log(longest.path, ', ', longest.length)
Here is the Java solution
import java.util.ArrayList;
public class LongestPath {
static class Node{
int data;
Node left = null;
Node right = null;
Node(int data){
this.data = data;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = new Node(1);
Node two = new Node(2);
Node three = new Node(3);
Node four = new Node(4);
Node five = new Node(5);
Node six = new Node(6);
root.left = two;
root.right = three;
three.left = four;
three.right = five;
four.left = six;
//printGraph(root);
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(root.data);
Node curr = root;
while(curr.left !=null || curr.right!=null){
if(checkDepth(curr.left)>=checkDepth(curr.right)){
arr.add(curr.left.data);
curr = curr.left;
System.out.println("Hello");
}
else {
arr.add(curr.right.data);
curr = curr.right;
System.out.println("Hello2");
}
//System.out.println(curr.data);
}
System.out.println(arr.toString());
}
static void printGraph(Node root){
if(root == null)
return;
System.out.println(root.data);
if(root.left != null){
printGraph(root.left);
}
if(root.right != null){
printGraph(root.right);
}
}
static int checkDepth(Node root){
if(root == null)
return 0;
return 1+ Math.max(checkDepth(root.left), checkDepth(root.right));
}
}
Time: O(n) Space: Constant
So here is the idea.
1. In the first iteration calculate the height and store it in a local variable.
2. In the second iteration send this height variable in the recursive method which returns true if this path has that height or returns false.
3. While returning from this method if the invocation of root.left or root.right returns true for this method, then we print the current node and return true so that its parent can be printed too.
public static boolean inLongestPath (Tree root, int height) {
if (root==null && height==0)
return true;
if (root==null)
return false;
if (inLongestPath(root.left, height) || inLongestPath(root.right, height)) {
System.out.println(root.val);
return true;
}
}
Hi guys, here is my working code, it only goes over the tree once, so it's O(n). It uses depth-first.
import java.util.ArrayList;
import java.util.List;
/**
* Created by nicolas on 1/11/17.
*/
public class LongestPath {
ArrayList<Node> longestPath = new ArrayList<>();
ArrayList<Node> currentPath = new ArrayList<>();
public static void main(String[] args){
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
node1.left = node2;
node1.right = node3;
Node node4 = new Node(4);
Node node5 = new Node(5);
node2.left = node4;
node2.right = node5;
Node node8 = new Node(8);
Node node9 = new Node(9);
node4.left = node8;
node4.right = node9;
Node node10 = new Node(10);
Node node11 = new Node(11);
node9.left = node10;
node9.right = node11;
Node node6 = new Node(6);
Node node7 = new Node(7);
node3.left = node6;
node3.right = node7;
System.out.println(new LongestPath().printLongestPath(node1));
}
List<Node> printLongestPath(Node node){
currentPath.add(node);
if(node.left == null && node.right == null){
if(currentPath.size() > longestPath.size()){
longestPath = (ArrayList)currentPath.clone();
}
return longestPath;
}
if(node.left != null){
printLongestPath(node.left);
currentPath.remove(currentPath.size()-1);
}
if(node.right != null){
printLongestPath(node.right);
currentPath.remove(currentPath.size()-1);
}
return longestPath;
}
}
class Node{
Node left;
Node right;
int value;
Node(int value){
this.value = value;
}
@Override
public String toString() {
return " " + value;
}
}
System.out.println("Longest path length => " + calcLongest(root, 1));
private static int calcLongest(BinaryTreeNode<Integer> node , int pathLength){
int leftLongest = pathLength;
if(node.left != null){
leftLongest = calcLongest(node.left, pathLength + 1);
}
int rightLongest = pathLength;
if(node.right != null){
rightLongest = calcLongest(node.right, pathLength + 1);
}
return Math.max(leftLongest, rightLongest);
}
int height(node* pnode)
{
if (NULL == pnode)
return 0;
int lh = height(pnode->left);
int rh = height(pnode->right);
return (1 + max(lh, rh));
}
void print_nodes(node* pnode)
{
node* pcurnode = pnode;
while(pcurnode)
{
print_node(pcurnode);
int lh = height(pcurnode->left);
int rh = height(pcurnode->right);
pcurnode = lh > rh ? pcurnode->left : pcurnode->right;
}
}
printing in reverse order but in single pass to tree using power of recursion
def longest_path(tree, longest_path_arr):
if tree:
lh = longest_path(tree.left, longest_path_arr)
rh = longest_path(tree.right, longest_path_arr)
if lh > rh:
if tree.left:
longest_path_arr.append(tree.left.val)
return 1 + lh
else:
if tree.right:
longest_path_arr.append(tree.right.val)
return 1 + rh
return 0
Here is my implementation in C#:
A sample Node class:
class Node<T>
{
public T Data;
public Node<T> LeftChild;
public Node<T> RightChild;
public Node()
{ }
public Node(T data)
{
this.Data = data;
}
}
Longest path Function:
public List<T> LongestPathFromRootToNode(Node<T> node)
{
if (node == null)
{
return new List<T>();
}
var left_subtree_path = LongestPathFromRootToNode(node.LeftChild);
var right_subtree_path = LongestPathFromRootToNode(node.RightChild);
if (left_subtree_path.Count >= right_subtree_path.Count)
{
left_subtree_path.Add(node.Data);
return left_subtree_path;
}
else
{
right_subtree_path.Add(node.Data);
return right_subtree_path;
}
}
public class LongestPath {
private String longestPath = null;
public static void main(String[] args) {
LongestPath instance = new LongestPath();
TreeNode rootNode = instance.createTree();
System.out.println("Longest path is : " + instance.getLongestPath(rootNode));
}
private TreeNode createTree(){
TreeNode rootNode = new TreeNode(0);
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
TreeNode node9 = new TreeNode(9);
TreeNode node10 = new TreeNode(10);
TreeNode node11 = new TreeNode(11);
TreeNode node12 = new TreeNode(12);
rootNode.setLeft(node1);
rootNode.setRight(node2);
node1.setLeft(node3);
node1.setRight(node4);
node3.setLeft(node5);
node3.setRight(node6);
node6.setRight(node7);
node5.setLeft(node8);
node2.setLeft(node9);
node9.setLeft(node10);
node10.setLeft(node11);
//node11.setRight(node12);
return rootNode;
}
private String getLongestPath(TreeNode rootNode){
if(rootNode==null)
return null;
String path ="";
getPath(path, rootNode);
return longestPath;
}
private Integer getPath(String path, TreeNode node) {
path+="/"+node.value;
if(node.left==null && node.right==null){
String tempPath = longestPath;
if(longestPath!=null && longestPath.contains(","))
tempPath = longestPath.split(",")[0];
if(tempPath==null || tempPath.split("/").length<path.split("/").length)
longestPath = path;
else if(tempPath.split("/").length == path.split("/").length)
longestPath+=","+path;
return 1;
}
if(node.left==null && node.right!=null)
return 1+ getPath(path, node.right);
else if( node.left!=null && node.right==null)
return 1+ getPath(path, node.left);
else
return 1+ Math.max(getPath(path,node.left), getPath(path, node.right) );
}
}
class TreeNode {
TreeNode left;
TreeNode right;
Integer value;
public TreeNode(Integer value) {
left = null;
right= null;
this.value = value;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public void setRight(TreeNode right) {
this.right = right;
}
@Override
public String toString() {
return "TreeNode [left=" + left + ", right=" + right + ", value=" + value + "]";
}
}
import bst
import random
def longest_path_length_bst(root):
if root is None:
return 0
return max(longest_path_length_bst(root.left), longest_path_length_bst(root.right)) + 1
def longest_path_bst(root):
if root is None:
return []
left_path = longest_path_bst(root.left)
right_path = longest_path_bst(root.right)
if len(right_path) > len(left_path):
max_path = right_path
else:
max_path = left_path
max_path.append(root.data)
return max_path
tree = bst.BST()
data = [random.randint(0, 1000000) for x in range(1000)]
tree.insert(data)
print longest_path_bst(tree.root)
import bst
import random
def longest_path_length_bst(root):
if root is None:
return 0
return max(longest_path_length_bst(root.left), longest_path_length_bst(root.right)) + 1
def longest_path_bst(root):
if root is None:
return []
left_path = longest_path_bst(root.left)
right_path = longest_path_bst(root.right)
if len(right_path) > len(left_path):
max_path = right_path
else:
max_path = left_path
max_path.append(root.data)
return max_path
tree = bst.BST()
data = [random.randint(0, 1000000) for x in range(1000)]
tree.insert(data)
print longest_path_bst(tree.root)
public Stack<Node> GetTallestNode(Node nd)
{
Stack<Node> lheight, rheight;
if (nd.Left != null)
{
lheight = GetTallestNode(nd.Left);
lheight.Push(nd);
}
else
{
lheight = new Stack<Node>();
lheight.Push(nd);
}
if (nd.Right != null)
{
rheight = GetTallestNode(nd.Right);
rheight.Push(nd);
}
else
{
rheight = new Stack<Node>();
rheight.Push(nd);
}
if (lheight.Count > rheight.Count)
{
return lheight;
}
else
{
return rheight;
}
}
public class Node
{
public Node (string val)
{
Value = val;
}
public string Value { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
public Stack<Node> GetTallestNode(Node nd)
{
Stack<Node> lheight, rheight;
if (nd.Left != null)
{
lheight = GetTallestNode(nd.Left);
lheight.Push(nd);
}
else
{
lheight = new Stack<Node>();
lheight.Push(nd);
}
if (nd.Right != null)
{
rheight = GetTallestNode(nd.Right);
rheight.Push(nd);
}
else
{
rheight = new Stack<Node>();
rheight.Push(nd);
}
if (lheight.Count > rheight.Count)
{
return lheight;
}
else
{
return rheight;
}
}
public class Node
{
public Node (string val)
{
Value = val;
}
public string Value { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
- neelabhsingh January 25, 2017My solution import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** *Longest Path from root to leaf Node * */ public class LongestPath { public static void main(String[] args) { BinaryTree bt = new BinaryTree(); Node root =bt.constructTree(bt); List path = printPath(root); Iterator itr = path.iterator(); while (itr.hasNext()){ System.out.print(itr.next() +" "); } } public static List<Integer> printPath(Node root){ if(root ==null){ return null; } List<Integer> path = new ArrayList<>(); path.add(root.data); List result = getMaxList(printPath(root.left), printPath(root.right)); if(result!=null) { path.addAll(result); } return path; } public static List<Integer> getMaxList(List<Integer> list1, List<Integer> list2){ if(list1==null && list2==null){ return null; } if(list1==null){ return list2; } if(list2 == null){ return list1; } if(list1.size()> list2.size()){ return list1; }else { return list2; } } } Binary Tree class Node { int data; Node left, right; Node(int item) { data = item; left = right = null; } } class BinaryTree { Node root; /* Get width of a given level */ int getWidth(Node node, int level) { if (node == null) return 0; if (level == 1) return 1; else if (level > 1) return getWidth(node.left, level - 1) + getWidth(node.right, level - 1); return 0; } /* UTILITY FUNCTIONS */ /* Compute the "height" of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int height(Node node) { if (node == null) return 0; else { /* compute the height of each subtree */ int lHeight = height(node.left); int rHeight = height(node.right); /* use the larger one */ return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1); } } /* Driver program to test above functions */ public Node constructTree( BinaryTree tree) { /* Constructed binary tree is: 1 / \ 2 3 / \ \ 4 5 8 / \ 6 7 */ tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.right = new Node(8); tree.root.right.right.left = new Node(6); tree.root.right.right.right = new Node(7); return tree.root; } } **OUTPUT** 1 3 8 7