Convert a ternary expression to a binary tree.
Say:
a?b:c to
a
/ \
b c
a?b?c:d:e to
a
/ \
b e
/ \
c d
Also, think about "a?b:c?d:e"
Let's assume the input ternary expression is valid, we can build the tree in preorder manner.
Each time we scan two characters, the first character is either ?
or :
, the second character holds the value of the tree node. When we see ?
, we add the new node to left. When we see :
, we need to find out the ancestor node that doesn't have a right node, and make the new node as its right child.
Time complexity is O(n)
.
public TreeNode convert(char[] expr) {
if (expr.length == 0) {
return null;
}
TreeNode root = new TreeNode(expr[0]);
Stack<TreeNode> stack = new Stack<>();
for (int i = 1; i < expr.length; i += 2) {
TreeNode node = new TreeNode(expr[i + 1]);
if (expr[i] == '?') {
stack.peek().left = node;
}
if (expr[i] == ':') {
stack.pop();
while (stack.peek().right != null) {
stack.pop();
}
stack.peek().right = node;
}
stack.push(node);
}
return root;
}
@jeantimex : Thanks. This solutions works considering we add root node on stack as others have suggested.
So, based on your algorithm, i have added a Python solution and a test case.
from commons.stack import Stack # import custom Stack class
class Node(object):
""" Tree Node """
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def inorder_tree(node, result):
""" Access Tree in-order """
if node is not None:
inorder_tree(node.left, result)
result.append(node.data)
inorder_tree(node.right, result)
def ternary_to_binary_tree(expression):
""" Convert ternary expression to Binary Tree """
if not expression:
return None
# Assuming the expression is of correct form
stack = Stack()
root = Node(expression[0])
stack.push(root)
for index in range(1, len(expression), 2):
operator = expression[index]
next_char = expression[index + 1]
node = Node(next_char)
if operator == "?":
stack.peek().left = node
if operator == ':':
stack.pop()
while(stack.peek().right != None):
stack.pop()
stack.peek().right = node
stack.push(node)
return root
if __name__ == '__main__':
test = "a?b?c:d:e"
root_node = ternary_to_binary_tree(test)
expected_result = ['c', 'b', 'd', 'a', 'e']
actual_result = []
# In-order traversal done to test the output
inorder_tree(node=root_node, result=actual_result)
assert expected_result == actual_result
@jeantimex
I'd like to ask why do we need the while loop here:
while (stack.peek().right != null) {
stack.pop();
}
If the input is valid, I think using two pop() instead of using the while loop would work. Is that right?
public TreeNode convert(char[] expr) {
if (expr.length == 0) {
return null;
}
TreeNode root=new TreeNode(expr[0]);
Stack<TreeNode> stack=new Stack<>();
queue.add(root);
for(int i=1;i<expr.length;i+=2){
if(expr[i]=='?'){
TreeNode node=new TreeNode(expr[i+1]);
stack.peek().left=node;
stack.push(node);
}else if(expr[i]==':'){
stack.pop();
TreeNode cur=stack.pop();
TreeNode node=new TreeNode(expr[i+1]);
cur.right=node;
stack.push(node);
}
}
return root;
}
@perfecttt I agree with you. I think your code is more intuitive. But I am not sure in the interview is there any test case that cannot pass through your code.
@perfecttt so the reason why we need that while loop is that imagine we have just filled up the rightmost child of a left subtree (in the examplee)
ie:
String input = "a?b?c?d:e:f?g:h:i?j:k"
imagine you just placed h into your tree, your current index is pointing to ":i" and thus are now trying to insert i- at that point your stack (from top to bottom) looks like h,f,b,a
we need to pop one node to remove a sibling node, and then keep popping nodes off till we reach a, which at this time has no right child (hence the whole while loop you are asking about)
hopefully that clears it up, but if not go ahead and trace through "a?b?c?d:e:f?g:h:i?j:k" for yourself:)
cheers!