Reproduce binary tree

tsv

3,331 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:

left -> root -> right (inorder)
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

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")

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content

Open Source Your Knowledge, Become a Contributor

Task

Solution

Tests

Longest substring in Python

PYTHON: BEGINNER QUIZ (10 Questions)

PYTHON STRING METHODS: center(), rjust() and ljust().

Python from Zero to Hero