__xy__
BAN USERFor trees structured differently, I don't think that a recursive solution is possible.
The iterative and recursive approaches differ in only the fact that who maintains the stack of nodes (found but yet to be processed).
In iterative, we maintain an explicit stack.
In recursive, an implicit stack is automatically maintained. All local variables are pushed onto stack when doing a new call and popped when returning from a call.
Now, when we are doing in order traversal, we keep pushing nodes onto stack till we have a left child. If no left child is present, we pop from the stack, visit it and then push the right child. We keep repeating this till the stack becomes empty.
If we have 2 trees with different structures, then we will have cases when we would want to push node for one tree and pop for the other.
This can be done in an iterative program where the stack is explicit and we have full control over it.
But, in recursive approach, for both trees one can do only the same operation (push or pop).
So, a recursive program does not seem possible here.
If it is given that the trees have same structure then I would go for a recursive approach.
A code like this should work:
public void alternateTraverse(Node root1, Node root2) {
if (root1 != null && root2 != null) {
alternateTraverse(root1.left, root2.left);
System.out.println("Tree1: " + root1.data);
System.out.println("Tree2: " + root2.data);
alternateTraverse(root1.right, root2.right);
}
}
But if they can have different structure, I would do an iterative inorder.
Also, what is the expectation if the trees have different number of nodes?
The problem is that your are visiting any node in the trees twice. For explanation, have a look at the following lines you wrote:
inOrderTraverse2(node1, node2.getLeft());
System.out.println(" "+node2.getData());
inOrderTraverse2(node1, node2.getRight());
Both the calls to inOrderTraverse2 are identical with respect to node1. inOrderTraverse2 is the function which prints node1's contents. So, node1's content will be printed twice.
- __xy__ February 22, 2014It appeared too simple to need any explanation.
Here is the Approach:
One needs to make any left subtree, a right subtree.
If the node has just left child, then just moving the child to right will complete the processing for that node.
If there is a right child too, then it should be made right child of the right-most of the original left subtree.
The above function process a node, and then returns the rightmost node of the transformed subtree.
private static Node transform(Node root) {
Node right = root.right;
Node rightMost = root;
if (root.left != null) {
rightMost = transform(root.left);
root.right = root.left;
root.left = null;
}
if (right == null) {
return rightMost;
}
rightMost.right = right;
rightMost = transform(right);
return rightMost;
}
Approach:
max path with a bend
=
max of {
max path with a bend of right subtree,
max path with a bend of left subtree,
max path with a bend including the root
}
In the above, max path with a bend including the root is the max of {
max of {length of left only path of right subtree, max length of right path of right subtree with one bend} + 1,
max of {length of right only path of left subtree, max length of left path of left subtree with one bend} + 1
}
Following code should work:
private static class State {
int max = 0; // max path with bend
int lpwb = 0; // left path with bend
int rpwb = 0; // right path with bend
int lpwob = 0; // left path without bend
int rpwob = 0; // right path without bend
}
private static class Node {
Node left;
Node right;
int data;
public Node(int d) {
data = d;
left = null;
right = null;
}
}
private static int max (int i, int j) {
return i > j ? i : j;
}
private static State getState(Node root) {
State s = new State();
if (root.left == null && root.right == null) {
return s;
}
State rs = root.right == null ? null : getState(root.right);
State ls = root.left == null ? null : getState(root.left);
s.lpwob = ls == null ? 0 : ls.lpwob + 1;
s.rpwob = rs == null ? 0 : rs.rpwob + 1;
s.lpwb = ls == null ? 0 : (max(ls.lpwb, ls.rpwob) + 1);
s.rpwb = rs == null ? 0 : (max(rs.rpwb, rs.lpwob) + 1);
if (s.lpwb < 2) { // a path with bend must be of length at least 2
s.lpwb = 0;
}
if (s.rpwb < 2) {
s.rpwb = 0;
}
s.max = max(s.lpwb, max(s.rpwb, max(rs == null ? 0 : rs.max, ls == null ? 0 : ls.max)));
return s;
}
leftmost node need not be a left node. A right node can also be the leftmost node for a level.
In my example, the 2nd level (assuming root to be level 1) has only one node (which is a right node).
So, it is the leftmost node for level 2 as there are no nodes to the left of it.
@lazylearner You are correct till "So probability of picking 2 block sock is: (1/2) * (11/23) = 11/46"
But your next statement is wrong.
Probability of picking 2 black socks = 11/46
On similar lines, probability of picking 2 white socks = 11/46
So, probability of picking either 2 black socks or 2 white socks = 11/46 + 11/46 = 11/23
public class GenerateCode{
private static char getCharacterForValue(int n) {
return (char)('A' + n - 1);
}
private static boolean isValidOneLengthString(String s) {
return Integer.parseInt(s) > 0;
}
private static boolean isValidTwoLengthString(String s) {
int val = Integer.parseInt(s);
return val > 9 && val < 27;
}
private static void generate(String prefix, String input) {
if (input.length() == 0) {
System.out.println(prefix);
return;
}
if (isValidOneLengthString(input.substring(0, 1))) {
generate(prefix + getCharacterForValue(Integer.parseInt(input.substring(0, 1))), input.substring(1));
}
if (input.length() > 1 && isValidTwoLengthString(input.substring(0, 2))) {
generate(prefix + getCharacterForValue(Integer.parseInt(input.substring(0, 2))), input.substring(2));
}
}
public static void main(String[] args){
generate("", "1123");
}
}
post order traversal.
- __xy__ February 01, 2016depth(tree) = 1 + max(depth (left-subtree), depth(right-subtree))
depth of leaf node is zero.