CareerCup

This seemed like an interesting problem, but as usual turned out be an incompletely defined dud.

Given the "leaf ordering", pre-order is not unique.

Consider the two trees:

A
    \
     B
    / \
   C   D
  
Preoder: ABCD

A
  / \
 C   B
      \
       D
  
Preorder: ACBD

The "leaf traversal" for both is

C D
B
A

I think we should consider it as BST and insert from last line to first line considering given characters as keys...

//Approach ::
//
// 1.In BST, all left nodes are smaller than root and all right nodes are greater than
// root
// 2.Preorder traversal is Node -> Left -> Right
//
// It is clear that last string in input must be root and first string must be leaves
// of original tree.
//
// Using above mention two points, we can divide first string from input array into two
// parts. Nodes in left of root are the part of leftTree and nodes in right of root are the
// part of rightTree.
// Now for all other input strings we just need to append character either in front of
// leftTree or rightTree

// Dry run for above approach on input strings : {"BDHPY","CM","GQ","K"}
//
// Last string is root so for this input "k" is root
// Now, in first string ("BDHPY"), will divide it according to point 1
// so, it will look like, "BDH" --> left sub tree & "PY" --> right sub tree
//
// Now start appending the characters according to point 1 for further input strings.
// So, second string it looks like, "CBDH" --> left tree & "MPY" --> right tree
// And son on, "GCBDH" --> left Tree & "QMPY" --> right Tree
//
// Now, according to point 2. the output strings look like, "KGCBDHQMPY"
// which is our expected output.

Assume given tree is BST:

Steps:

for lineN to 1:
	if treeExists
		insert nodes one by one in this tree in BST form.
	else
		create root node with given element

//you will have a complete BST now...
//Use preorder() to draw preorder string of BST

I got an approach but it gives a different pre order traversal...any other hint given??

is the given pre order traversal correct ?

@ Arunkumar I myself got a different pre-order. And this is the complete question. No other hint (apart from the example itself).

@ Anonymous: That's the only test case given!

Though, while discussing with one of my friends we got an approach that can produce the same pre-order given in the example.
1. pop left most character in line, add it to first leaf from left.
2. pop right most character in line, add to first leaf from right.

This way you add first child in all leaf nodes, before adding their second child.

Though in the absence of additional test cases, its all speculative. Hope someone has a better answer.

I assume this is a full binary tree. Otherwise, we will need a way to represent null nodes in a level, e.g. 'space' character.
With this assumption, the following logic should work.
* allocate an array with the size=total_nodes+1.
* Read each line from right to left
* Fill the array with each character from the end of the array (i.e. right to left).
* At the end of this, you should have the original binary tree represented as array.
* Now we should be able to do a pre-order traversal.
* Start the array traversal at index 1 ( this is the root element).
* Recursively do the following.
* Visit the node ( node at index).
* Visit left( node at 2*index).
* Visit right( node at 2*index+1).

This is the simplest what I can think of.
There might be other ways if we treat each line as level order traversal queue. But it will be complex.

k
							/		\
							G		Q
						     /       \		/    \
						    c       h	     m	p
						    /\				 \
					           bd				 y

So its a normal binary tree or Binary Search Tree. On looking into example, I think it is binary search tree

The Given Sequence is more kind of sorted order..
BDHPY 
CM 
GQ 
K
step 1:
B D H P Y

step 2: next level of leaves, we know k is a root.

   C          M
 /   \          /  \
B  D  H  P  Y
As b is less than c, and greater than D. H is less than K(root) and more than c.(However it falls in left branch of K). then M greater than K.. similarly P<M<Y
 
step 3:Like wise.. then now try preoder reverse.
           K
         /   \
       G    Q
       /  \     \
    C    H    M
 /   \          /  \
B  D      P  Y

I could solve this problem and all test cases were running successfully.

The code for this is as below,

public static class Node {
		String val = null;
		Node left = null;
		Node right = null;

		Node(String v) {
			val = v;
		}

		public String toString() {
			return val;
		}
	}

	public void preOrderTraversal(Node node) {
		if (node == null) {
			return;
		}
		System.out.print(node.val);
		preOrderTraversal(node.left);
		preOrderTraversal(node.right);
	}

	public void inserNode(String val, Node node) {
		if (node == null) {
			return;
		}
		Node parent = searchParent(val, node);
		Node child = new Node(val);
		if (val.compareTo(parent.val) > 0) {
			parent.right = child;
		} else if (val.compareTo(parent.val) < 0) {
			parent.left = child;
		}
	}

	public Node searchParent(String val, Node node) {
		Node parent = null;
		if (node == null) {
			return null;
		}
		if (node != null) {
			if (val.compareTo(node.val) > 0) {
				if (node.right == null) {
					return node;
				}
				parent = searchParent(val, node.right);
			} else if (val.compareTo(node.val) < 0) {
				if (node.left == null) {
					return node;
				}
				parent = searchParent(val, node.left);
			}
		}
		return parent;
	}