Reproduce binary tree

tsv
1,139 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Task

Binary tree is traversed twise:

  1. left -> root -> right (inorder)
  2. root -> left -> right (preorder)

Having two arrays you need to reconstruct this binary tree

Solution

Implemented in python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def make_tree(inorder, preorder):
if inorder is None:
raise TypeError("inorder is None")
if preorder is None:
raise TypeError("preorder is None")
if len(inorder) != len(preorder):
raise ValueError("length mismatch")
return make_tree_impl(inorder, preorder)
def make_tree_impl(inorder, preorder):
if len(inorder) == 0 or len(preorder) == 0:
return None
val = preorder[0]
i = inorder.find(val)
if i < 0:
return make_tree_impl(inorder, preorder[1:])
node = Node(val)
node.left = make_tree_impl(inorder[:i], preorder[1:])
node.right = make_tree_impl(inorder[i + 1:], preorder[1:])
return node
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Tests

Implemented in python
from impl import make_tree
def send_msg(channel, msg):
print("TECHIO> message --channel \"{}\" \"{}\"".format(channel, msg))
def success():
print("TECHIO> success true")
def fail():
print("TECHIO> success false")
def dump_tree_inorder(node):
if node is None:
return ""
left = dump_tree_inorder(node.left)
right = dump_tree_inorder(node.right)
return "{0}{1}{2}".format(node.value, left, right)
def test_case(inorder, preorder):
root = make_tree(inorder, preorder)
actual = dump_tree_inorder(root)
msg = "Running make_tree('{0}', '{1}')... Expected '{1}', got '{2}'"
assert preorder == actual, msg.format(inorder, preorder, actual)
def expect_type_error(inorder, preorder):
try:
make_tree(inorder, preorder)
raise AssertionError("expect type error")
except TypeError:
pass
def expect_value_error(inorder, preorder):
try:
make_tree(inorder, preorder)
raise AssertionError("expect value error")
except ValueError:
pass
def test_make_tree():
try:
test_case("dbeafcg", "abdecfg")
test_case("dcba", "abcd")
test_case("abcd", "abcd")
test_case("", "")
expect_type_error(None, "abc")
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content