Binary Tree

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. The binary tree is a recursive structure, as each child can also be the root of its own binary tree.

Example: Let's create a binary tree and perform some operations on it.

# Node class definition
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Creating a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Tree traversal - In-order traversal
def inorder_traversal(node):
    if node is None:
        return
    inorder_traversal(node.left)
    print(node.value, end=" ")
    inorder_traversal(node.right)

# Perform in-order traversal
inorder_traversal(root)
# Output: 4 2 5 1 3

In this example, we define a Node class that represents a node in the binary tree. Each node has a value and two child pointers (left and right) initialized as None.

We create a binary tree by linking nodes together using the child pointers. In this case, we have a tree with root value 1, its left child with value 2, its right child with value 3, and further nodes beneath them.

To traverse the binary tree, we define an inorder_traversal function that performs an in-order traversal. In in-order traversal, we recursively visit the left subtree, print the value of the current node, and then recursively visit the right subtree. The output is the values of the nodes visited in the order: left, root, right.

Let's solve a question using the concept of a binary tree. The question is "Binary Tree Inorder Traversal," which requires returning the in-order traversal of a given binary tree.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def inorder_traversal(root):
    if not root:
        return []

    result = []
    stack = []
    curr = root

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left

        curr = stack.pop()
        result.append(curr.value)
        curr = curr.right

    return result

# Creating a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Perform in-order traversal
print(inorder_traversal(root))
# Output: [4, 2, 5, 1, 3]

In this solution, we use an iterative approach to perform an in-order traversal. We maintain a stack to keep track of the nodes to visit. Starting from the root, we traverse the left subtree by repeatedly moving to the left child and pushing the nodes onto the stack. Once we reach a leaf node (current node is None), we backtrack by popping a node from the stack, adding its value to the result, and moving to its right child.

The time complexity of the solution is O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is O(h), where h is the height of the binary tree, as the maximum size of the stack is determined by the height of the tree. In the worst case, when the tree is skewed, the height is O(n), resulting in O(n) space complexity.