Amazon Interview Question Software Engineers
Country: United States
Time Complexity is O(N) where N is number of elements in Binary tree. If it is a BST then time complexity can be reduced to O(log n)
Note: **This code won't work if Nodes in binary tree were to have 2 or more digit number**
public class TargetNumber {
public static Node findStartNode(int num,Node root){
if(root!=null){
if(root.data==num){
return root;
}else{
Node left=findStartNode(num,root.left);
Node right=findStartNode(num, root.right);
return (left!=null) ? left : right;
}
}else{
return null;
}
}
public static boolean path(Node root,String num){
//find the start node. for ex "47" find node where 4 exists
int startNum=Character.getNumericValue(num.charAt(0));
Node start=findStartNode(startNum, root);
//return false if no node exists with startNum
for(int i=1;i<num.length();i++){
if(start!=null){
if(start.left!=null && start.left.data==Character.getNumericValue(num.charAt(i))){
start=start.left;
}else if (start.right!=null && start.right.data==Character.getNumericValue(num.charAt(i))){
start=start.right;
}else{
start=null;
}
}else{
return false;
}
}
return (start==null) ? false : true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//this method returns
Node root=new Node(3);
root.left=new Node(4);
root.right=new Node(5);
root.left.left=new Node(6);
root.left.right=new Node(7);
root.right.left=new Node(8);
root.right.right=new Node(9);
if(path(root, "10")){
System.out.println("True");
}else{
System.out.println("False");
}
}
}
// Assume we store the binary tree in 1D array
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[7] = { 3, 4, 5, 6, 7, 8, 9 };
int targ = 359, sz = 7;
queue<pair<int, int> > q;
q.push(make_pair(0, targ));
while (!q.empty()) {
int curIdx = q.front().first;
int curVal = arr[q.front().first];
int curTarg = q.front().second;
// cout << curTarg << " " << curIdx << " " << curVal << endl;
q.pop();
stringstream ss;
ss << curTarg;
stringstream ss2;
ss2 << curVal;
string remTargStr = ss.str();
if (ss.str().find(ss2.str()) == 0) {
remTargStr = ss.str().substr(ss2.str().length());
if (remTargStr.length() == 0) {
cout << "YES" << endl;
return 0;
}
} else if (curTarg < targ)
continue;
stringstream ss3;
ss3 << remTargStr;
int remTarg;
ss3 >> remTarg;
if (curIdx * 2 + 1 < sz) {
q.push(make_pair(curIdx * 2 + 1, remTarg));
if (curIdx * 2 + 2 < sz)
q.push(make_pair(curIdx * 2 + 2, remTarg));
}
}
cout << "NO" << endl;
return 0;
}
public boolean isNumberExist(TreeNode<Integer> root, int[] numArray, int index) {
TreeNode<Integer> tempRoot = findRoot(root, numArray[0]);
if (tempRoot != null && numArray.length == 1) {
return true;
} else {
return isPathExist(tempRoot, numArray, 0);
}
}
private boolean isPathExist(TreeNode<Integer> tempRoot, int[] numArray, int index) {
if (tempRoot == null) {
return index == numArray.length;
} else {
if (tempRoot.getData() == numArray[index]) {
index++;
boolean flag = isPathExist(tempRoot.getLeftChild(), numArray, index);
if (!flag && index != numArray.length)
flag = isPathExist(tempRoot.getRightChild(), numArray, index);
return flag;
}
return false;
}
}
private TreeNode<Integer> findRoot(TreeNode<Integer> root, int num) {
if (root == null) {
return null;
} else if (root.getData() == num) {
return root;
} else {
TreeNode<Integer> temp = findRoot(root.getLeftChild(), num);
if (temp == null)
temp = findRoot(root.getRightChild(), num);
return temp;
}
}
bool BinaryTree::pathExists(string searchTerm, int curI=0, node *curNode=root) {
//cout<<"\n pathExists() : "<<curI<<" ";
if(curI > searchTerm.length())
return false; //erroneus state
if(curNode == NULL)
return false;
//cout<<curNode->ch;
char ch = searchTerm[curI];
bool flag = false;
// continue existing path
if(curNode->ch == ch) {
if(curI == searchTerm.length()-1) {
return true;
}
flag = pathExists(searchTerm, curI+1, curNode->left) || pathExists(searchTerm, curI+1, curNode->right);
if(flag)
return true;
}
// start new path from here
if(curNode->ch == searchTerm[0]) {
flag = pathExists(searchTerm, 1, curNode->left) || pathExists(searchTerm, 1, curNode->right);
if(flag)
return true;
}
// try to start path in descendants
flag = pathExists(searchTerm, 0, curNode->left) || pathExists(searchTerm, 0, curNode->right);
return flag;
}
you can split target into int collection.
// Get All Digit in collection
public static List<int> AllDigit(int number)
{
List<int> allDigits = new List<int>();
int reminder = number;
while(reminder != 0)
{
allDigits.Add(reminder%10);
reminder=reminder/10;
}
return allDigits;
}
//Check path available or not
//startNode = find the first node from where you have to start.
public static bool checkPath(BNode startNode, List<int> targetNumber, int index)
{
if(index < 0)
return true;
if(startNode == null)
return false;
if(startNode.data == targetNumber[index])
{
bool left = checkPath(startNode.left, targetNumber, index-1);
bool right = checkPath(startNode.right, targetNumber, index-1);
return left || right;
}
else
return false;
}
# python
import sys
class Node(object):
def __init__(self, val):
self.l = None
self.r = None
self.val = val
def find_pattern(target, root, index=0):
target = str(target)
if index >= len(target):
return True
if root is None:
return False
if target[index] == str(root.val):
index += 1
elif target[0] == str(root.val):
index = 1
else:
index = 0
return find_pattern(
target, root.l, index) or find_pattern(target, root.r, index)
if __name__ == '__main__':
root = Node(3)
root.l = Node(4)
root.l.l = Node(6)
root.l.r = Node(7)
root.r = Node(5)
root.r.l = Node(8)
root.r.r = Node(9)
print find_pattern(sys.argv[1], root)
namespace T3
{
class Node
{
public Node Left { get; set; }
public Node Right { get; set; }
public int Id { get; set; }
}
class Program
{
static private List<Node> nodes = null;
static private void MakeNodes()
{
//3
//45
//6789
nodes = new List<Node>(7);
for (int i = 0; i < 7; ++i) nodes.Add(null);
nodes[6] = new Node { Left = null, Right = null, Id = 6};
nodes[5] = new Node { Left = null, Right = null, Id = 7};
nodes[4] = new Node { Left = null, Right = null, Id = 8};
nodes[3] = new Node { Left = null, Right = null, Id = 9};
nodes[2] = new Node { Left = null, Right = null, Id = 4};
nodes[1] = new Node { Left = null, Right = null, Id = 5};
//conventionally we know that nodes[0] is root
nodes[0] = new Node { Left = null, Right = null, Id = 3};
//arranging nodes in a tree
nodes[0].Left = nodes[2];
nodes[0].Right = nodes[1];
nodes[2].Left = nodes[6];
nodes[2].Right = nodes[5];
nodes[1].Right = nodes[4];
nodes[1].Right = nodes[3];
}
static private Node FindFirst(int Id)
{
foreach (Node node in nodes)
{
if (node.Id == Id) return node;
}
return null;
}
static private Node FindNextValid(Node current, int Id)
{
if (null == current.Left) return null;
if (null == current.Right) return null;
if (current.Left.Id == Id) return current.Left;
if (current.Right.Id == Id) return current.Right;
return null;
}
static private bool VerifyPath(int[] data)
{
if (null == data) return false;
if (0 == data.Length) return false;
Node current = FindFirst(data[0]);
if (null == current)
{
return false;
}
else
{
int pos = 1;
while (true)
{
if (pos == data.Length) return true;
else current = FindNextValid(current, data[pos]);
if (null == current) return false;
else pos += 1;
}
}
}
static void Main(string[] args)
{
MakeNodes();
Console.WriteLine(VerifyPath(new int[] { 6 }));
Console.WriteLine(VerifyPath(new int[] { 16 }));
Console.WriteLine(VerifyPath(null));
Console.WriteLine(VerifyPath(new int[] { 4, 7 }));
Console.WriteLine(VerifyPath(new int[] { 3, 8 }));
Console.WriteLine(VerifyPath(new int[] { 3, 5, 9 }));
Console.WriteLine(VerifyPath(new int[] { 3, 4, 6 }));
}
}
}
class Node {
public Node left;
public Node right;
public int data;
Node(int d) {
this.data = d;
this.left = null;
this.right = null;
}
}
public class Solution {
static int numDigits(int n) {
int d = 0;
while (n > 0) {
n /= 10;
d++;
}
return d;
}
static int extractFront(int front, int num) {
int nDigits = numDigits(num);
int fDigits = numDigits(front);
if (nDigits == 0 || fDigits == 0 || nDigits < fDigits) {
return -1;
}
return (num % (int)(Math.pow(10, nDigits - fDigits)));
}
static boolean digitMatch(int larger, int smaller) {
if (smaller == 0) {
return false;
}
while (larger > 0) {
if (larger == smaller) {
return true;
}
larger /= 10;
}
return false;
}
static boolean pathWithTarget(Node root, int n) {
return pathWithTarget(root, n, true);
}
static boolean pathWithTarget(Node root, int n, boolean original) {
if (root == null) {
return false;
}
if (root.data == n) {
return true;
}
if (root.data < n) {
if (digitMatch(n, root.data)) {
int extracted = extractFront(root.data, n);
if (pathWithTarget(root.left, extracted, false)) {
return true;
}
if (pathWithTarget(root.right, extracted, false)) {
return true;
}
return false;
}
}
if (original) {
if (pathWithTarget(root.left, n, true)) {
return true;
}
if (pathWithTarget(root.right, n, true)) {
return true;
}
}
return false;
}
public static void main(String []args) {
Node n3 = new Node(32);
Node n4 = new Node(4);
n3.left = n4;
Node n5 = new Node(5);
n3.right = n5;
Node n6 = new Node(6);
n4.left = n6;
Node n7 = new Node(7);
n4.right = n7;
Node n8 = new Node(8);
n5.left = n8;
Node n9 = new Node(9);
n5.right = n9;
System.out.println(Solution.pathWithTarget(n3, 3248, true));
}
}
public boolean includesPath(int p){
path = p;
return helper(head,"");
}
private boolean helper(Node n, String previous){
if (n == null) return false;
String current = previous+Integer.toString(n.value);
System.out.println(current +" "+ Integer.toString(path));
if (current.equals(Integer.toString(path))) return true;
return helper(n.left,current) || helper(n.right,current);
}
public boolean includesPath(int p){
path = p;
return helper(head,"");
}
private boolean helper(Node n, String previous){
if (n == null) return false;
String current = previous+Integer.toString(n.value);
System.out.println(current +" "+ Integer.toString(path));
if (current.equals(Integer.toString(path))) return true;
return helper(n.left,current) || helper(n.right,current);
}
Time Complexity : O(N*h*log(h^2)), where N = number of nodes and h = ht. of tree
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#define pb push_back
using namespace std ;
map<string , bool> mp ;
struct Node
{
int data;
struct Node* left, *right;
};
struct Node* newNode(int data)
{
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return (newNode);
}
void PreOrder(Node *root , string str)
{
if(root == NULL)
return ;
int x = root -> data ;
char ch = x + '0' ;
str.pb(ch) ;
mp[str] = true ;
int len = str.size() ;
for(int i = 0 ; i < len ; i++)
{
for(int j = i ; j < len ; j++)
{
string tmp = str.substr(i , j) ;
if(mp[tmp] == false)
mp[tmp] = true ;
}
}
PreOrder(root -> left , str) ;
PreOrder(root -> right , str) ;
}
int main()
{
struct Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->right->right = newNode(8);
root->right->left->left = newNode(9);
string tmp = "" ;
PreOrder(root , tmp) ;
for(map<string , bool>::iterator it = mp.begin() ; it != mp.end() ; ++it)
cout << it -> first << ' ' ;
return 0 ;
}
public List<Integer> getTargetDigits(int target) {
List<Integer> allDigits = new ArrayList<Integer>();
int reminder = target;
while (reminder > 0) {
allDigits.add(reminder % 10);
reminder = reminder / 10;
}
return allDigits;
}
public boolean checkPath(BNode startNode, List<Integer> targetDigits, int index) {
if (index == -1) {
return true;
}
while (startNode != null) {
if (startNode.val == targetDigits.get(index)) {
boolean left = checkPath(startNode.left, targetDigits, index - 1);
boolean right = checkPath(startNode.right, targetDigits, index - 1);
return left || right;
} else {
boolean left = checkPath(startNode.left, targetDigits, targetDigits.size() -1 );
boolean right = checkPath(startNode.right, targetDigits, targetDigits.size() - 1);
return left || right;
}
}
return false;
}
public class PathMatchNumber {
public static void main(String[] args) {
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node3.left = node4; node3.right = node5;
Node node6 = new Node(6);
Node node7 = new Node(7);
node4.left = node6; node4.right = node7;
Node node8 = new Node(8);
Node node9 = new Node(9);
node5.left = node8; node5.right = node9;
System.out.println(match(node3, 359));
System.out.println(match(node3, 38));
System.out.println(match(node3, 47));
System.out.println(match(node3, 6));
}
private static Node match(Node node, Integer number) {
return matchNode(node, String.valueOf(number));
}
private static Node matchNode(Node node, String number) {
boolean matched = matchPath(node, number);
if (matched) return node;
Node matchedNode = null;
if (node.left != null) matchedNode = matchNode(node.left, number);
if (matchedNode != null) return matchedNode;
if (node.right != null) matchedNode = matchNode(node.right, number);
if (matchedNode != null) return matchedNode;
return null;
}
private static boolean matchPath(Node node, String number) {
final String value = String.valueOf(node.value);
if (!number.startsWith(value)) return false;
if (number.length() == value.length()) return true;
// otherwise
boolean matched = false;
if (node.left != null) matched = matchPath(node.left, number.substring(value.length()));
if (matched) return true;
// otherwise
if (node.right != null) matched = matchPath(node.right, number.substring(value.length()));
if (matched) return true;
// otherwise
return false;
}
private static class Node {
private Node left;
private Node right;
private final Integer value;
private Node(Integer value) {
this.value = value;
}
public String toString() {
return String.valueOf(value);
}
}
}
This will work on BST with time complexity of O(n) where n is the size of the tree.
private static boolean pathExist(String target, TreeNode treeNode) {
return pathExist(treeNode, target, false);
}
private static boolean pathExist(TreeNode treeNode, String target, boolean pathStarted) {
if (target.length() == 0)
return true;
if (treeNode == null) return false;
String dataAsString = String.valueOf(treeNode.data);
boolean targetStartsWithData = target.startsWith(dataAsString);
if (pathStarted && !targetStartsWithData) {
return false;
}
if (targetStartsWithData) {
pathStarted = true;
target = target.substring(dataAsString.length());
}
return pathExist(treeNode.left, target, pathStarted)
|| pathExist(treeNode.right, target, pathStarted);
}
Simple solution -
Step 1- Find the node with first element of the given array
if node is present then go for step 2
else No path is present
Step 2-
Check for the remaining elements of the given array in child tree of the node.
If any level with no match elements then return false.
else keep matching for remaining elements of array and return true on all match found
I think that there's a trick question here that everyone missed here. Your solutions work if it's digits but fail if it's any think longer.
The trick question (and I think that is way they gave simple examples) is that you search for sub numbers, meaning if the tree is: 5->64->23->77 and the target is "2377" you don't only need to check 2->3->7->7 but also, 2->3->77, 2->377, 23->7->7, 23->77, 237->7, 2->37->7.
In most of the implementations I saw here this is not being taken under consideration.
this is my implementation using javascript. Notice I used BST only because I had already implemented the function to create the tree for another question :D, but my solution doesn't actually need it to be BST
function buildTree(arr) {
const root = new Node(arr[0]);
for (let i = 1; i < arr.length; i++) {
root.insert(new Node(arr[i]));
}
return root;
}
function printTree(node) {
let arr = [node];
while (arr.length) {
let tmp = [];
let level = '';
for (let n of arr) {
level += ` ${n.data} `;
if (n.left) tmp.push(n.left);
if (n.right) tmp.push(n.right);
}
console.log(level);
arr = tmp;
}
}
//I build a BST, even thou I don't have to in the question
let root = buildTree([5, 3, 7, 1, 4, 6, 8, 2, 9, 10,22,65,23,44,664]);
printTree(root);
function findPath(root, target){
return findRoot(root,createDigitsArray(target), 0);
}
function checkPath(root, arr, index){
if(index >= arr.length){
return true;
}
let number = 0;
while(index < arr.length){
number *= 10;
number += arr[index];
if(root.left && root.left.data === number){
let found = checkPath(root.left, arr, index + 1);
if (found){
return true;
}
}
if(root.right && root.right.data === number){
let found = checkPath(root.right, arr, index + 1);
if (found){
return true;
}
}
index++;
}
return false;
}
function findRoot(root, arr, index){
if(index >= arr.length){
return;
}
let number = 0;
while(index < arr.length){
number *= 10;
number += arr[index];
let startPoint = findStartPoint(root, number);
if(startPoint){
let found = checkPath(startPoint, arr, index + 1);
if(found){
return true;
}
}
index++;
}
return false;
}
function createDigitsArray(num){
const arr = [];
while(num > 0){
arr.unshift(num % 10);
num = Math.floor(num / 10);
}
return arr;
}
function findStartPoint(root, number){
if(!root){
return;
}
if(root.data === number){
return root;
}
let found = findStartPoint(root.left, number);
return found || findStartPoint(root.right, number);
}
console.log('found',findPath(root,652344)); //return true
console.log('found',findPath(root,662344)); //return false
console.log('found',findPath(root,312)); //return true
I forgot the class for the Tree Node :D
class Node {
constructor(data) {
this.data = data;
}
insert(node) {
if (node.data < this.data) {
if (!this.left) {
this.left = node;
} else {
this.left.insert(node);
}
} else {
if (!this.right) {
this.right = node;
} else {
this.right.insert(node);
}
}
}
}
{ // without repeated numbers
static class Node {
Node(int v, Node l, Node r) {
this.val = v;
this.left = l;
this.right = r;
}
int val;
Node left;
Node right;
}
private static int hasPathValidate(Node n, int num) {
if (n == null)
return 1;
int left = hasPathValidate(n.left, num);
if (num / left == 0)
return left;
if (n.val == (num%(left*10))/left)
return left*10;
int right = hasPathValidate(n.right, num);
if (num / right == 0)
return right;
if (n.val == (num%(right*10))/right)
return right*10;
return 1;
}
public static boolean hasPath(Node n, int num) {
return hasPathValidate(n, num) > 1;
}
@Test
public void test() {
Temp.Node n6 = new Temp.Node(6,null,null);
Temp.Node n7 = new Temp.Node(7,null,null);
Temp.Node n8 = new Temp.Node(8,null,null);
Temp.Node n9 = new Temp.Node(9,null,null);
Temp.Node n4 = new Temp.Node(4,n6,n7);
Temp.Node n5 = new Temp.Node(5,n8,n9);
Temp.Node n3 = new Temp.Node(3,n4,n5);
Assert.assertTrue(Temp.hasPath(n3,359));
Assert.assertFalse(Temp.hasPath(n3,38));
Assert.assertTrue(Temp.hasPath(n3,34));
Assert.assertTrue(Temp.hasPath(n3,47));
Assert.assertTrue(Temp.hasPath(n3,6));
}}
{ @Test}
{ public void tG() {}
{ Temp.Node n6 = new Temp.Node(6,null,null);}
{ Temp.Node n7 = new Temp.Node(7,null,null);}
{ Temp.Node n8 = new Temp.Node(8,null,null);}
{ Temp.Node n9 = new Temp.Node(9,null,null);}
{ Temp.Node n4 = new Temp.Node(4,n6,n7);}
{ Temp.Node n5 = new Temp.Node(5,n8,n9);}
{ Temp.Node n3 = new Temp.Node(3,n4,n5);}
{}
{ Assert.assertTrue(Temp.hasPath(n3,359));}
{ Assert.assertFalse(Temp.hasPath(n3,38));}
{ Assert.assertTrue(Temp.hasPath(n3,34));}
{ Assert.assertTrue(Temp.hasPath(n3,47));}
{ Assert.assertTrue(Temp.hasPath(n3,6));}
{ }}
{private static int hasPathValidate(Node n, int num) {}
{ if (n == null)}
{ return 1;}
{ int left = hasPathValidate(n.left, num);}
{ if (num / left == 0)}
{ return left;}
{ if (n.val == (num%(left*10))/left)}
{ return left*10;}
{ int right = hasPathValidate(n.right, num);}
{ if (num / right == 0)}
{ return right;}
{ if (n.val == (num%(right*10))/right)}
{ return right*10;}
{ return 1;}
{}}
{public static boolean hasPath(Node n, int num) {}
{ return hasPathValidate(n, num) > 1;}
{}}
public class CareerCup_Amazon_FindGivenNumberInTree {
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode(0);
TreeNode o1 = new TreeNode(1);
TreeNode t2 = new TreeNode(1);
TreeNode t3 = new TreeNode(3);
TreeNode f4 = new TreeNode(4);
TreeNode f5 = new TreeNode(4);
TreeNode s6 = new TreeNode(6);
TreeNode s7 = new TreeNode(7);
TreeNode e8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
root.left = o1;
root.right = t2;
o1.left = t3;
o1.right = f4;
t2.left = f5;
t2.right = s6;
t3.left = s7;
t3.right = e8;
f5.left = n9;
CareerCup_Amazon_FindGivenNumberInTree o = new CareerCup_Amazon_FindGivenNumberInTree();
o.hasNumberInTree(root,149);
}
public boolean hasNumberInTree(TreeNode root,Integer n){
List<Integer> nL = new ArrayList<>();
while(!(n<10)){
int nR = n%10;
n = n/10;
nL.add(0,nR);
}
nL.add(0,n);
return hasNumberInTreeHelper(root,nL,-1,0,0);
}
/* ex:
3
4 5
6 7 8 9*/
public boolean hasNumberInTreeHelper(TreeNode root,List<Integer> nL,int previosLevel,int level,int i){
if(root==null)
return false;
if(root.val == nL.get(i)){
if(previosLevel==-1)
previosLevel = level;
else if(level-previosLevel>1)
return false;
previosLevel = level;
i=i+1;
}
if(i==nL.size()){
return true;
}
if(hasNumberInTreeHelper(root.left, nL,previosLevel,level+1,i) || hasNumberInTreeHelper(root.right, nL,previosLevel,level+1,i))
return true;
return false;
}
}
public class CareerCup_Amazon_FindGivenNumberInTree {
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode(0);
TreeNode o1 = new TreeNode(1);
TreeNode t2 = new TreeNode(1);
TreeNode t3 = new TreeNode(3);
TreeNode f4 = new TreeNode(4);
TreeNode f5 = new TreeNode(4);
TreeNode s6 = new TreeNode(6);
TreeNode s7 = new TreeNode(7);
TreeNode e8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
root.left = o1;
root.right = t2;
o1.left = t3;
o1.right = f4;
t2.left = f5;
t2.right = s6;
t3.left = s7;
t3.right = e8;
f5.left = n9;
CareerCup_Amazon_FindGivenNumberInTree o = new CareerCup_Amazon_FindGivenNumberInTree();
o.hasNumberInTree(root,149);
}
public boolean hasNumberInTree(TreeNode root,Integer n){
List<Integer> nL = new ArrayList<>();
while(!(n<10)){
int nR = n%10;
n = n/10;
nL.add(0,nR);
}
nL.add(0,n);
return hasNumberInTreeHelper(root,nL,-1,0,0);
}
/* ex:
3
4 5
6 7 8 9*/
public boolean hasNumberInTreeHelper(TreeNode root,List<Integer> nL,int previosLevel,int level,int i){
if(root==null)
return false;
if(root.val == nL.get(i)){
if(previosLevel==-1)
previosLevel = level;
else if(level-previosLevel>1)
return false;
previosLevel = level;
i=i+1;
}
if(i==nL.size()){
return true;
}
if(hasNumberInTreeHelper(root.left, nL,previosLevel,level+1,i) || hasNumberInTreeHelper(root.right, nL,previosLevel,level+1,i))
return true;
return false;
}
}
public class CareerCup_Amazon_FindGivenNumberInTree {
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode(0);
TreeNode o1 = new TreeNode(1);
TreeNode t2 = new TreeNode(1);
TreeNode t3 = new TreeNode(3);
TreeNode f4 = new TreeNode(4);
TreeNode f5 = new TreeNode(4);
TreeNode s6 = new TreeNode(6);
TreeNode s7 = new TreeNode(7);
TreeNode e8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
root.left = o1;
root.right = t2;
o1.left = t3;
o1.right = f4;
t2.left = f5;
t2.right = s6;
t3.left = s7;
t3.right = e8;
f5.left = n9;
CareerCup_Amazon_FindGivenNumberInTree o = new CareerCup_Amazon_FindGivenNumberInTree();
o.hasNumberInTree(root,149);
}
public boolean hasNumberInTree(TreeNode root,Integer n){
List<Integer> nL = new ArrayList<>();
while(!(n<10)){
int nR = n%10;
n = n/10;
nL.add(0,nR);
}
nL.add(0,n);
return hasNumberInTreeHelper(root,nL,-1,0,0);
}
/* ex:
3
4 5
6 7 8 9*/
public boolean hasNumberInTreeHelper(TreeNode root,List<Integer> nL,int previosLevel,int level,int i){
if(root==null)
return false;
if(root.val == nL.get(i)){
if(previosLevel==-1)
previosLevel = level;
else if(level-previosLevel>1)
return false;
previosLevel = level;
i=i+1;
}
if(i==nL.size()){
return true;
}
if(hasNumberInTreeHelper(root.left, nL,previosLevel,level+1,i) || hasNumberInTreeHelper(root.right, nL,previosLevel,level+1,i))
return true;
return false;
}
public class CareerCup_Amazon_FindGivenNumberInTree {
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode(0);
TreeNode o1 = new TreeNode(1);
TreeNode t2 = new TreeNode(1);
TreeNode t3 = new TreeNode(3);
TreeNode f4 = new TreeNode(4);
TreeNode f5 = new TreeNode(4);
TreeNode s6 = new TreeNode(6);
TreeNode s7 = new TreeNode(7);
TreeNode e8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
root.left = o1;
root.right = t2;
o1.left = t3;
o1.right = f4;
t2.left = f5;
t2.right = s6;
t3.left = s7;
t3.right = e8;
f5.left = n9;
CareerCup_Amazon_FindGivenNumberInTree o = new CareerCup_Amazon_FindGivenNumberInTree();
o.hasNumberInTree(root,149);
}
public boolean hasNumberInTree(TreeNode root,Integer n){
List<Integer> nL = new ArrayList<>();
while(!(n<10)){
int nR = n%10;
n = n/10;
nL.add(0,nR);
}
nL.add(0,n);
return hasNumberInTreeHelper(root,nL,-1,0,0);
}
/* ex:
3
4 5
6 7 8 9*/
public boolean hasNumberInTreeHelper(TreeNode root,List<Integer> nL,int previosLevel,int level,int i){
if(root==null)
return false;
if(root.val == nL.get(i)){
if(previosLevel==-1)
previosLevel = level;
else if(level-previosLevel>1)
return false;
previosLevel = level;
i=i+1;
}
if(i==nL.size()){
return true;
}
if(hasNumberInTreeHelper(root.left, nL,previosLevel,level+1,i) || hasNumberInTreeHelper(root.right, nL,previosLevel,level+1,i))
return true;
return false;
}
}
public class CareerCup_Amazon_FindGivenNumberInTree {
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode(0);
TreeNode o1 = new TreeNode(1);
TreeNode t2 = new TreeNode(1);
TreeNode t3 = new TreeNode(3);
TreeNode f4 = new TreeNode(4);
TreeNode f5 = new TreeNode(4);
TreeNode s6 = new TreeNode(6);
TreeNode s7 = new TreeNode(7);
TreeNode e8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
root.left = o1;
root.right = t2;
o1.left = t3;
o1.right = f4;
t2.left = f5;
t2.right = s6;
t3.left = s7;
t3.right = e8;
f5.left = n9;
CareerCup_Amazon_FindGivenNumberInTree o = new CareerCup_Amazon_FindGivenNumberInTree();
o.hasNumberInTree(root,149);
}
public boolean hasNumberInTree(TreeNode root,Integer n){
List<Integer> nL = new ArrayList<>();
while(!(n<10)){
int nR = n%10;
n = n/10;
nL.add(0,nR);
}
nL.add(0,n);
return hasNumberInTreeHelper(root,nL,-1,0,0);
}
/* ex:
3
4 5
6 7 8 9*/
public boolean hasNumberInTreeHelper(TreeNode root,List<Integer> nL,int previosLevel,int level,int i){
if(root==null)
return false;
if(root.val == nL.get(i)){
if(previosLevel==-1)
previosLevel = level;
else if(level-previosLevel>1)
return false;
previosLevel = level;
i=i+1;
}
if(i==nL.size()){
return true;
}
if(hasNumberInTreeHelper(root.left, nL,previosLevel,level+1,i) || hasNumberInTreeHelper(root.right, nL,previosLevel,level+1,i))
return true;
return false;
}
}
public boolean hasNumberInTree(TreeNode root,Integer n){
List<Integer> nL = new ArrayList<>();
while(!(n<10)){
int nR = n%10;
n = n/10;
nL.add(0,nR);
}
nL.add(0,n);
return hasNumberInTreeHelper2(root,nL,0);
}
/* ex:
3
4 5
6 7 8 9*/
public boolean hasNumberInTreeHelper2(TreeNode root,List<Integer> nL,int i){
if(root==null)
return false;
if(i==nL.size()-1 && root.val==nL.get(nL.size()-1))
return true;
if(root.val == nL.get(i)){
return hasNumberInTreeHelper2(root.left, nL, i+1) ||
hasNumberInTreeHelper2(root.right, nL, i+1);
}else{
if(root.val == nL.get(0)){
return hasNumberInTreeHelper2(root.left, nL, 1) ||
hasNumberInTreeHelper2(root.right, nL, 1) ;
}else{
return hasNumberInTreeHelper2(root.left, nL, 0) ||
hasNumberInTreeHelper2(root.right, nL, 0) ;
}
}
}
public class CareerCup_Amazon_FindGivenNumberInTree { public static void main(String[] args) { // TODO Auto-generated method stub TreeNode root = new TreeNode(0); TreeNode o1 = new TreeNode(1); TreeNode t2 = new TreeNode(1); TreeNode t3 = new TreeNode(3); TreeNode f4 = new TreeNode(4); TreeNode f5 = new TreeNode(4); TreeNode s6 = new TreeNode(6); TreeNode s7 = new TreeNode(7); TreeNode e8 = new TreeNode(8); TreeNode n9 = new TreeNode(9); root.left = o1; root.right = t2; o1.left = t3; o1.right = f4; t2.left = f5; t2.right = s6; t3.left = s7; t3.right = e8; f5.left = n9; CareerCup_Amazon_FindGivenNumberInTree o = new CareerCup_Amazon_FindGivenNumberInTree(); o.hasNumberInTree(root,149); } public boolean hasNumberInTree(TreeNode root,Integer n){ List<Integer> nL = new ArrayList<>(); while(!(n<10)){ int nR = n%10; n = n/10; nL.add(0,nR); } nL.add(0,n); return hasNumberInTreeHelper(root,nL,-1,0,0); } /* ex: 3 4 5 6 7 8 9*/ public boolean hasNumberInTreeHelper(TreeNode root,List<Integer> nL,int previosLevel,int level,int i){ if(root==null) return false; if(root.val == nL.get(i)){ if(previosLevel==-1) previosLevel = level; else if(level-previosLevel>1) return false; previosLevel = level; i=i+1; } if(i==nL.size()){ return true; } if(hasNumberInTreeHelper(root.left, nL,previosLevel,level+1,i) || hasNumberInTreeHelper(root.right, nL,previosLevel,level+1,i)) return true; return false; }}
- SK January 07, 2017