4. Binary Tree Types

Binary Tree Types¶

1. Full or Proper Binary Tree: https://www.programiz.com/dsa/full-binary-tree
2. Perfect Binary Tree: https://www.programiz.com/dsa/perfect-binary-tree
3. Complete Binary Tree: https://www.programiz.com/dsa/complete-binary-tree
4. Balanced Binary Trees

In [7]:

from utils.nodes import BinaryTreeNode as Node
from utils.tree_traversal import TreeTraversal as tt
from utils.tree_type_check import TreeTypeCheck as tc
from utils.tree_properties import count_nodes, calculate_depth, get_height
from utils.tree_properties import (
    get_height,
    get_height_concise,
    is_balanced_naive,
    is_balanced_optimized_driver,
)

from utils.nodes import BinaryTreeNode as Node from utils.tree_traversal import TreeTraversal as tt from utils.tree_type_check import TreeTypeCheck as tc from utils.tree_properties import count_nodes, calculate_depth, get_height from utils.tree_properties import ( get_height, get_height_concise, is_balanced_naive, is_balanced_optimized_driver, )

1. Full or Proper Binary Tree¶

In [8]:

class FullBinaryTree(Node):
    pass

class FullBinaryTree(Node): pass

In [9]:

root = FullBinaryTree(1)

root = FullBinaryTree(1)

In [10]:

root.left = Node(2)
root.right = Node(3)

root.left.left = Node(4)
root.left.right = Node(5)

root.left.right.left = Node(6)
root.left.right.right = Node(7)

# uncomment to get an imperfect tree
# root.left.right.right.left = Node(10)

root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.left.right.left = Node(6) root.left.right.right = Node(7) # uncomment to get an imperfect tree # root.left.right.right.left = Node(10)

In [11]:

tt.traverse_preorder(root)

tt.traverse_preorder(root)

1
2
4
5
6
7
3

In [12]:

tc.is_full_tree(root)

tc.is_full_tree(root)

Out[12]:

True

2. Perfect Binary Tree¶

In [13]:

class PerfectBinaryTree(Node):
    pass

class PerfectBinaryTree(Node): pass

In [14]:

root = PerfectBinaryTree(1)
root.left = Node(2)
root.right = Node(3)

root.left.left = Node(4)
root.left.right = Node(5)

root.right.left = Node(6)
root.right.right = Node(7)

root = PerfectBinaryTree(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7)

In [15]:

calculate_depth(root)

calculate_depth(root)

Out[15]:

3

In [16]:

count_nodes(root)

count_nodes(root)

Out[16]:

7

In [17]:

tc.is_perfect_using_depth(root, calculate_depth(root))

tc.is_perfect_using_depth(root, calculate_depth(root))

Out[17]:

True

In [18]:

count_nodes(root)

count_nodes(root)

Out[18]:

7

In [19]:

tc.is_perfect_using_length(root)

tc.is_perfect_using_length(root)

Out[19]:

False

3. Complete Binary Tree¶

In [20]:

class CompleteBinaryTree(Node):
    pass

class CompleteBinaryTree(Node): pass

Tree 1¶

In [21]:

root = CompleteBinaryTree(1)

root.left = Node(12)
root.right = Node(9)

root.left.left = Node(5)
root.left.right = Node(6)

# root.right.left = Node(10)

root = CompleteBinaryTree(1) root.left = Node(12) root.right = Node(9) root.left.left = Node(5) root.left.right = Node(6) # root.right.left = Node(10)

Tree 2¶

In [22]:

root = CompleteBinaryTree(10)

root.left = Node(20)
root.right = Node(30)

root.left.left = Node(40)
root.left.right = Node(50)

root.right.left = Node(1)
root.right.right = Node(2)

root.left.left.left = Node(3)

root.left.right.left = Node(100)

root = CompleteBinaryTree(10) root.left = Node(20) root.right = Node(30) root.left.left = Node(40) root.left.right = Node(50) root.right.left = Node(1) root.right.right = Node(2) root.left.left.left = Node(3) root.left.right.left = Node(100)

Level Order Traversal¶

In [23]:

tt.print_level_order_traversal_recursive(root)

tt.print_level_order_traversal_recursive(root)

10
20
30
40
50
1
2
3
100

In [24]:

tt.level_order_traversal_iterative(root)

tt.level_order_traversal_iterative(root)

Out[24]:

[10, 20, 30, 40, 50, 1, 2, 3, 100]

Check completeness¶

Method 1¶

In [25]:

index = 0
num_nodes = count_nodes(root)
tc.is_complete(root, index, num_nodes)

index = 0 num_nodes = count_nodes(root) tc.is_complete(root, index, num_nodes)

Out[25]:

False

Method 2¶

In [26]:

tc.is_complete_using_level_order(root)

tc.is_complete_using_level_order(root)

Out[26]:

False

4. Balanced Binary Tree¶

In [27]:

root = Node(1)

root.left = Node(2)
root.right = Node(3)

root.left.left = Node(4)
root.left.right = Node(5)

# comment this node to balance
root.left.left.left = Node(8)

root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) # comment this node to balance root.left.left.left = Node(8)

In [28]:

get_height(root)

get_height(root)

Out[28]:

4

In [29]:

get_height_concise(root)

get_height_concise(root)

Out[29]:

4

In [30]:

is_balanced_naive(root)

is_balanced_naive(root)

Out[30]:

False

In [31]:

is_balanced_optimized_driver(root)

is_balanced_optimized_driver(root)

Tree is not balanced

In [ ]: