Assuming each node has self.left, self.right and self.data, whats the best way to construct a binary tree, not a binary search tree (BST), from a list where the numbers are given per level. Where the first number is level 1, next 2 are level 2, next 4 are level 3, and so on. For example

input: [3,5,2,1,4,6,7,8,9,10,11,12,13,14] 

constructs a tree:

 3 / \ 5 2 /\ /\ 1 4 6 7 /\ /\ /\ /\ 8 9 10 11 12 13 14

One solution is:

for node at index i,
left child index = 2i+1
right child index = 2i+2

Wondering if there are other possible ways

1

5 Answers

You can directly use this tool: drawtree by pip install drawtree, and if you are curious about its implementation you can refer to this source code: .

For your case in the question:

from drawtree import draw_level_order
draw_level_order('[3,5,2,1,4,6,7,8,9,10,11,12,13,14]')

And you will get the text graph like the following:

 3 / \ / \ / \ / \ / \ / \ / \ / \ 5 2 / \ / \ / \ / \ / \ / \ 1 4 6 7 / \ / \ / \ /
8 9 / \ / \ 14 10 11 12 13

In addition, you can try Graphviz.

1

class TreeNode: def __init__(self, val: int, left=None, right=None) -> None: self.val = val self.left = left self.right = right def __repr__(self) -> str: return f"val: {self.val}, left: {self.left}, right: {self.right}" def __str__(self) -> str: return str(self.val)
def to_binary_tree(items: list[int]) -> TreeNode: """Create BT from list of values.""" n = len(items) if n == 0: return None def inner(index: int = 0) -> TreeNode: """Closure function using recursion bo build tree""" if n <= index or items[index] is None: return None node = TreeNode(items[index]) node.left = inner(2 * index + 1) node.right = inner(2 * index + 2) return node return inner()

Usage:

root = to_binary_tree([1, 2, 3, None, None, 4, 5])

One way to do it is to build a fringe of the current leaves.

Assuming a Node class:

class Node(object): def __init__(self, data): self.data = data self.left = '*' self.right = '*' def __str__(self): return f'<{self.data}, {self.left}, {self.right}>' # Py 3.6

Then you can just manage the fringe and iterate over the data:

from collections import deque
data = [3,5,2,1,4,6,7,8,9,10,11,12,13,14]
n = iter(data)
tree = Node(next(n))
fringe = deque([tree])
while True: head = fringe.popleft() try: head.left = Node(next(n)) fringe.append(head.left) head.right = Node(next(n)) fringe.append(head.right) except StopIteration: break
print(tree)
# <3, <5, <1, <8, *, *>, <9, *, *>>, <4, <10, *, *>, <11, *, *>>>, <2, <6, <12, *, *>, <13, *, *>>, <7, <14, *, *>, *>>>

1

Here is a quick solution I came up with:

class BT_Node: def __init__(self, data): self.data = data self.left = None self.right = None def __str__(self): return f'<{self.data}, {self.left}, {self.right}>'
def build_binary_tree(values, index): if len(values) == 0: raise Exception('Node list is empty') if index > len(values) - 1: raise Exception('Index out of range') root = BT_Node(values[index]) if 2*index+1 < len(values): root.left = build_binary_tree(values, 2*index+1) if 2*index+2 < len(values): root.right = build_binary_tree(values, 2*index+2) return root

2

Here is one way to implement your solution: create a list of tree nodes, each with index position corresponding to the original data list. Then, we can fix up the left- and right links.

import logging
logging.basicConfig(level=logging.DEBUG)
logger = logging.getLogger(__name__)
class Tree(object): def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def __repr__(self): left = None if self.left is None else self.left.data right = None if self.right is None else self.right.data return '(D:{}, L:{}, R:{})'.format(self.data, left, right)
def build_tree_breadth_first(sequence): # Create a list of trees forest = [Tree(x) for x in sequence] # Fix up the left- and right links count = len(forest) for index, tree in enumerate(forest): left_index = 2 * index + 1 if left_index < count: tree.left = forest[left_index] right_index = 2 * index + 2 if right_index < count: tree.right = forest[right_index] for index, tree in enumerate(forest): logger.debug('[{}]: {}'.format(index, tree)) return forest[0] # root
def main(): data = [3, 5, 2, 1, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14] root = build_tree_breadth_first(data) print 'Root is:', root
if __name__ == '__main__': main()

Output:

DEBUG:__main__:[0]: (D:3, L:5, R:2)
DEBUG:__main__:[1]: (D:5, L:1, R:4)
DEBUG:__main__:[2]: (D:2, L:6, R:7)
DEBUG:__main__:[3]: (D:1, L:8, R:9)
DEBUG:__main__:[4]: (D:4, L:10, R:11)
DEBUG:__main__:[5]: (D:6, L:12, R:13)
DEBUG:__main__:[6]: (D:7, L:14, R:None)
DEBUG:__main__:[7]: (D:8, L:None, R:None)
DEBUG:__main__:[8]: (D:9, L:None, R:None)
DEBUG:__main__:[9]: (D:10, L:None, R:None)
DEBUG:__main__:[10]: (D:11, L:None, R:None)
DEBUG:__main__:[11]: (D:12, L:None, R:None)
DEBUG:__main__:[12]: (D:13, L:None, R:None)
DEBUG:__main__:[13]: (D:14, L:None, R:None)
Root is: (D:3, L:5, R:2)

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy