Binary Tree¶

⏱ Time-Complexity¶

The following table sums up all the different public functionality in this class and also provides the worst-case time complexity along side with the optimal time complexity that I will try to reach in future releases Insha’Allah. Generally, we are going to use the following indicators in the table:

• n is the number of nodes currently in the binary tree.

BinaryTreeNode()¶

Here are all of the public methods that can be used with BinaryTreeNode() objects:

class extra.trees.binary_tree.BinaryTreeNode(value)¶

A binary tree node is the basic unit for building binary trees. A binary tree node must contain a value and this value can’t be None. Each binary tree node has either zero, one or two children binary tree nodes. The node that has no children is called a leaf node.

__init__(value)¶

Creates a BinaryTreeNode() object which is the basic unit for building BinaryTree() objects!!

Parameters:	value (object) – The value to be saved within the BinaryTreeNode() instance
Raises:	ValueError: – If the given item is None. TypeError: – If the given item is an Extra() object.

Example

>>> x = BinaryTreeNode(10)
>>> x
BinaryTreeNode(10)
>>> type(x)
<class 'extra.trees.binary_tree.BinaryTreeNode'>

You can’t initialize a BinaryTreeNode() using a None

>>> BinaryTreeNode(None)
ValueError: Can't use `None` as an element within             `extra.BinaryTreeNode()`!!

__repr__()¶

Represents BinaryTreeNode() object as a string.

Returns:	A string representing the BinaryTreeNode() instance.
Return type:	str

Example

>>> x = BinaryTreeNode(10)
>>> x
BinaryTreeNode(10)

get_children()¶

Returns a list of all the children of the current BinaryTreeNode() instance.

Returns:	A list of all the children of the BinaryTreeNode() instance.
Return type:	list

Example

>>> x = BinaryTreeNode(2021)
>>> x.set_left(BinaryTreeNode("Hello"))
>>> x.set_right(BinaryTreeNode("World"))
>>> x.get_children()
[BinaryTreeNode(Hello), BinaryTreeNode(World)]

get_data()¶

Returns the data stored in the BinaryTreeNode() instance.

Returns:	The object stored in the BinaryTreeNode().
Return type:	object

Example

>>> x = BinaryTreeNode(10)
>>> x.get_data()
10

get_left()¶

Returns the left-child of the current BinaryTreeNode() instance.

Returns:	The left child of the current BinaryTreeNode(). And None if the current BinaryTreeNode() doesn’t have a left child.
Return type:	BinaryTreeNode() or None

Example

>>> x = BinaryTreeNode(2021)
>>> x.set_left(BinaryTreeNode("Hello"))
>>> x.set_right(BinaryTreeNode("World"))
>>> x.get_left()
BinaryTreeNode(Hello)

get_right()¶

Returns the right-child of the current BinaryTreeNode() instance.

Returns:	The right child of the current BinaryTreeNode(). And None if the current BinaryTreeNode() doesn’t have a right child.
Return type:	BinaryTreeNode()

Example

>>> x = BinaryTreeNode(2021)
>>> x.set_left(BinaryTreeNode("Hello"))
>>> x.set_right(BinaryTreeNode("World"))
>>> x.get_right()
BinaryTreeNode(World)

has_one_child()¶

Checks if the current BinaryTreeNode() has only one child. This child can be the left or the right one.

Returns:	True if the current BinaryTreeNode() has only one child. False if it has either zero or two children.
Return type:	bool

Example

>>> x = BinaryTreeNode(2021)
>>> x.has_one_child()
False
>>> x.set_left(BinaryTreeNode("Hello"))
>>> x.has_one_child()
True
>>> x.set_right(BinaryTreeNode("World"))
>>> x.has_one_child()
False

is_leaf()¶

Checks if the current BinaryTreeNode() instance is a leaf node. A leaf node is a tree node that has no children.

Returns:	True if the current BinaryTreeNode() has no children and False otherwise.
Return type:	bool

Example

>>> x = BinaryTreeNode("hello")
>>> x.is_leaf()
True
>>> x.set_right(BinaryTreeNode("world"))
>>> x.is_leaf()
False

set_left(new_node)¶

Sets the given BinaryTreeNode() as a left child for the current BinaryTreeNode().

Parameters:	child (BinaryTreeNode()) – The BinaryTreeNode() that will be a left child for the current one.
Raises:	TypeError: – If the given item is not an BinaryTreeNode() object.

Example

>>> x = BinaryTreeNode(2021)
>>> x.set_left(BinaryTreeNode("Hello"))
>>> x.get_left()
BinaryTreeNode("Hello")

A child has to be a BinaryTreeNode() object:

>>> x.set_left(2)
TypeError: You can't set a child unless it's an             `extra.BinaryTreeNode()` object!!

set_right(new_node)¶

Sets the given BinaryTreeNode() as a right child for the current BinaryTreeNode().

Parameters:	child (BinaryTreeNode()) – The BinaryTreeNode() that will be a right child for the current one.
Raises:	TypeError: – If the given item is not an BinaryTreeNode() object.

Example

>>> x = BinaryTreeNode(2021)
>>> x.set_right(BinaryTreeNode("World"))
>>> x.get_right()
BinaryTreeNode("World")

A child has to be a BinaryTreeNode() object:

>>> x.set_right(2)
TypeError: You can't set a child unless it's an             `extra.BinaryTreeNode()` object!!

BinaryTree()¶

Here are all of the public methods that can be used with BinaryTree() objects:

class extra.trees.binary_tree.BinaryTree¶

A binary tree is a non-linear data structure that can be defined recursively using a collection of BinaryTreeNode() instances, where each node has either zero, one or two references to the children BinaryTreeNode() instances.

__contains__(value)¶

Searches the BinaryTree() for the given value and returns True if the value exists and False if not.

Parameters:	value (object) – The value to be searched for in the BinaryTree() instance.
Returns:	Returns True if the value exists in the BinaryTree() instance and False if not.
Return type:	bool

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> 2 in btree
True
>>> "hello" in btree
False

__init__()¶

Creates an empty BinaryTree() object!!

Example

>>> t = BinaryTree()
>>> type(t)
<class 'extra.trees.binary_tree.BinaryTree'>

__iter__()¶

Iterates over the BinaryTree() instance and returns a generator of the BinaryTreeNode() values in breadth-first manner.

Yields:	Object – The value stored inside each node in the instance.

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> for value in btree:
...     print(value, end=',')
1,2,3,4,5,6,7,

__len__()¶

Gets the length of the BinaryTree() instance in time-complexity of O(n) where n is the number of nodes in the tree. Length is the number of nodes in the instance.

Returns:	The length of the BinaryTree() instance. Length is the number of tree nodes in the instance.
Return type:	int

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> len(btree)
7

__repr__()¶

Represents the BinaryTree() instance as a string.

Returns:	The string-representation of the BinaryTree() instance.
Return type:	str

Example

>>> btree = BinaryTree()
>>> btree
/ \
>>> # the following is a simple family tree
>>> root = BinaryTreeNode("GrandFather")
>>> left_child = BinaryTreeNode("Father")
>>> left_child.set_left(BinaryTreeNode("You"))
>>> left_child.set_right(BinaryTreeNode("Sibling"))
>>> root.set_left(left_child)
>>>
>>> right_child = BinaryTreeNode("Uncle")
>>> right_child.set_left(BinaryTreeNode("Cousin1"))
>>> right_child.set_right(BinaryTreeNode("Cousin2"))
>>> root.set_right(right_child)
>>> btree._root = root
>>> btree
        ___________GrandFather_________
       /                               \
   _Father___                      ___Uncle__
  /          \                   /           \
You        Sibling             Cousin1      Cousin2

breadth_first_traverse()¶

Traverses the BinaryTree() instance in breadth-first manner. Which means that the tree nodes will be visited level by level.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.breadth_first_traverse()
[1, 2, 3, 4, 5, 6, 7]

clear()¶

Removes all nodes within the BinaryTree() instance in constant time.

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.clear()
>>> btree
/ \
>>> btree.is_empty()
True

count_leaf_nodes()¶

Counts the number of leaf nodes in the BinaryTree() instance. Leaf nodes are the tree nodes that have no children.

Returns:	A positive integer representing the number of leaf nodes in the BinaryTree().
Return type:	int

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.count_leaf_nodes()
4

depth_first_traverse()¶

Traverses the BinaryTree() instance in depth-first manner. Which means that the parent is visited first. Then, the left subtree (if found), then the right subtree (if found).

Note

It’s the same as preorder_traverse() method.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.depth_first_traverse()
[1, 2, 4, 5, 3, 6, 7]

get_depth()¶

Gets the depth of the BinaryTree() instance.

Returns:	A positive integer representing the depth of the instance.
Return type:	int

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.get_depth()
0

get_height()¶

Gets the height of the BinaryTree() instance. The tree’s height is the number of edges between the root and the furthest leaf node.

Returns:	A positive integer representing the height of the instance.
Return type:	int

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.get_height()
2

get_leftside_view()¶

Returns a list of all binary treenode values seen from the left side of the tree. So, given the root of a binary tree, imagine yourself standing on the left side of it, we should return all seen values from the left side.

Returns:	A list of all node values seen from the right side of the binary tree. These values are ordered by depth. So, the first value is of depth 0, the second value is of depth 1, and so on.
Return type:	list

Example

>>> btree = BinaryTree.parse([1, [2, 4, [5, 8]], [3, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    /
4   5   7
   /
  8
>>> btree.get_leftside_view()
[1, 2, 4, 8]

get_nodes_per_level()¶

Retrieves all tree nodes within the BinaryTree() instance so that all tree nodes in a certain level will be concatenated into a separate list.

Returns:	A nested list where the first inner-list has all the tree nodes in the first level, the second inner-list has all the tree nodes in the second level, … so on.
Return type:	list

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.get_nodes_per_level()
[[1], [2, 3], [4, 5, 6, 7]]

get_rightside_view()¶

Returns a list of all binary treenode values seen from the right side of the tree. So, given the root of a binary tree, imagine yourself standing on the right side of it, we should return all seen values from the right side.

Returns:	A list of all node values seen from the right side of the binary tree. These values are ordered by depth. So, the first value is of depth 0, the second value is of depth 1, and so on.
Return type:	list

Example

>>> btree = BinaryTree.parse([1, [2, 4, [5, 8]], [3, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    /
4   5   7
   /
  8
>>> btree.get_rightside_view()
[1, 3, 7, 8]

inorder_traverse()¶

Traverses the BinaryTree() instance in in-order manner. Which means that the left subtree (if found) is visited first. Then, the parent then the right subtree (if found).

Returns:	A list of all values of the in-order visited nodes.
Return type:	list

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.inorder_traverse()
[4, 2, 5, 1, 6, 3, 7]

invert()¶

Inverts the BinaryTree() instance O(log(n)) time. Inverting a binary tree means to switch sides as shown in the following example:

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5   6   7
>>> btree.invert()
>>> btree
    __1__
   /     \
  3       2
 / \    / \
7   6   5   4

is_balanced()¶

Checks if the BinaryTree() instance is balanced. A binary tree is balanced if the difference between the depth of any two leaf nodes is less than or equal to one.

Returns:	True if the BinaryTree() instance is balanced and False if it is not balanced.
Return type:	bool
Raises:	UserWarning: – If the BinaryTree() is empty.

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3]])
>>> btree
    __1__
   /     \
  2       3
 / \
4   5
>>> btree.is_balanced()
True

is_empty()¶

Checks if the BinaryTree() instance is empty or not in constant time.

Returns:	A boolean flag showing if the BinaryTree() instance is empty or not. True shows that this instance is empty and False shows it’s not empty.
Return type:	bool

Example

>>> btree = Tree()
>>> btree.is_empty()
True
>>> btree._root = BinaryTreeNode(1)
>>> btree.is_empty()
False

is_perfect()¶

Checks if the BinaryTree() instance is perfect. A binary tree is perfect if all its levels are completely filled.

Returns:	True if the BinaryTree() instance is perfect and False if it is not perfect.
Return type:	bool
Raises:	UserWarning: – If the BinaryTree() is empty.

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3]])
>>> btree
    __1__
   /     \
  2       3
 / \
4   5
>>> btree.is_perfect()
False
>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.is_perfect()
True

is_strict()¶

Checks if the BinaryTree() instance is strict. A binary tree is staict if all its all its non-leaf nodes have two children (left and right).

Returns:	True if the BinaryTree() instance is strict and False if it is not strict.
Return type:	bool
Raises:	UserWarning: – If the BinaryTree() is empty.

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3]])
>>> btree
    __1__
   /     \
  2       3
 / \
4   5
>>> btree.is_strict()
True

static parse(lst)¶

A static method that Creates a BinaryTree() instance from a nested list where the each element has a nested list represening a subtree where the first element in the parent and the second element is the left subtree and the third element is the right subtree.

Parameters:	lst (list or tuple) – A list or tuple object representing the tree in a linear-form.
Returns:	The root of the BinaryTree() instance formed from parsing the given object.
Return type:	BinaryTreeNode()
Raises:	ValueError: – If the given object can’t be parsed

Example

>>> x = ["PP", ["ADP", "in"], ["NP", ["PRON", "my"], ["Noun", "home"]]]
>>> btree = BinaryTree.parse(x)
>>> btree
      _PP_________
     /            \
  _ADP           __NP______
 /              /          \
in           _PRON       __Noun
            /           /
           my         home

postorder_traverse()¶

Traverses the BinaryTree() instance in post-order manner. Which means that the left subtree (if found) is visited first. Then, the right subtree (if found) then the parent.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.postorder_traverse()
[4, 5, 2, 6, 7, 3, 1]

preorder_traverse()¶

Traverses the BinaryTree() instance in pre-order manner. Which means that the parent is visited first. Then, the left subtree (if found), then the right subtree (if found).

Note

It’s the same as depth_first_traverse() method.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.preorder_traverse()
[1, 2, 4, 5, 3, 6, 7]

to_list()¶

Converts the BinaryTree() instance to a list where values will be inserted in breadth-first manner.

Returns:	A list object containing the same elements as the BinaryTree() instance.
Return type:	list

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.to_list()
[1, 2, 3, 4, 5, 6, 7]

traverse(method='inorder')¶

Traversal is the process to visit all nodes of a binary tree starting from the root as we cannot randomly access any node in a binary tree. There are four ways which we use to traverse a binary tree:

1. preorder - depth-first
2. inorder
3. posteorder
4. breadth-first

Parameters:	method (str (default="inorder")) – A lower-cased string describing the type of traversal that will be used. It could be one of these values: [“inorder”, “postorder”, “preorder”, “depth-first”, “breadth-first”]
Returns:	A list of all values of the visited nodes according to the specified traversal method.
Return type:	list
Raises:	ValueError: If the given method isn’t known. TypeError: If the given method isn’t a string.

Example

>>> btree = BinaryTree.parse([1, [2, 4, 5], [3, 6, 7]])
>>> btree
    __1__
   /     \
  2       3
 / \    / \
4   5    6  7
>>> btree.traverse("preorder")
[1, 2, 4, 5, 3, 6, 7]
>>> btree.traverse("inorder")
[4, 2, 5, 1, 6, 3, 7]
>>> btree.traverse("postorder")
[4, 5, 2, 6, 7, 3, 1]
>>> btree.traverse("breadth-first")
[1, 2, 3, 4, 5, 6, 7]
>>> btree.traverse("extra")
ValueError: Given traverse method has to be one of these:
{'breadth-first', 'postorder', 'inorder', 'depth-first', 'preorder'}