1over0
BAN USERJava solution using DFS inorder traversal but using a Stack to keep track on predecessor, so space complexity could be bad here. Any other simpler, recursion-only solution is welcome :-)
/*
* j PREORDER: j f a d h o m
* / \ INORDER: a d f h j m o
* / \
* / \
* f o
* / \ / \
* a h m
* / \
* d
*
* Returns true if the item is found and its
* predecessor(null inclusive) found
*/
public boolean inorderPredecessor(Node node, T item, Stack<Node> stk) {
if (node == null)
return false;
if (inorderPredecessor(node.left, item, stk))
return true;
if (item.compareTo(node.item) == 0) {
T pred = stk.isEmpty() ? null : stk.pop().item;
System.out.printf("inorder-pred of %s is %s\n", item, pred);
return true;
} else {
stk.push(node);
}
if (inorderPredecessor(node.right, item, stk))
return true;
return false;
}
public void inorderPredecessor(Node root, T item) {
if (root == null) {
System.out.printf("InorderPredecessor: Tree empty");
return;
}
Stack<Node> stk = new Stack<Node>();
if (!inorderPredecessor(root, item, stk)) {
System.out.printf("inorder-pred of %s was not found\n", item);
}
}
Few test case outputs:
inorder-pred of j is h
inorder-pred of f is d
inorder-pred of o is m
inorder-pred of a is null
inorder-pred of h is f
inorder-pred of m is j
inorder-pred of d is a
inorder-pred of k was not found
inorder-pred of z was not found
Repjoyceeallard, Associate at Adap.tv
Hi, i am working as a training manager as a business professional who assesses the growth and development needs of ...
Repmerrillagreerm, Android Engineer at Abs india pvt. ltd.
I am patient, compassionate, and caring when treating and counseling patients in practice, making them feel like they’re in ...
Repharrylseay, Aghori Mahakal Tantrik at ASAPInfosystemsPvtLtd
I am Harry and I live in the USA but basically I am from Bangor. I live my life very ...
RepHi, I am Alisa from Southfield, USA, I am working as a Toolmaker in an Audio-Visions company. I am also ...
RepRaimeCarrillo, Area Sales Manager at 247quickbookshelp
Hi, I am Raime from Tampa USA . I work as an Local account executive employee. I work in many fields ...
RepAnnetteFlynn, Android test engineer at ABC TECH SUPPORT
Hello I am a skill trainer. Master's Degree in Industrial and Organisational Psychology and 10 years of experience working ...
Here is a Java solution with test cases folks.
And the output:
- 1over0 March 25, 2014