Basic Binary Tree

Example: Let's create a basic 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 the 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 basic binary tree. The question is "Binary Tree Maximum Path Sum," which requires finding the maximum path sum in a binary tree.

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

class Solution:
    def max_path_sum(self, root):
        def max_path_sum_helper(node):
            nonlocal max_sum

            if node is None:
                return 0

            left_sum = max(max_path_sum_helper(node.left), 0)
            right_sum = max(max_path_sum_helper(node.right), 0)

            current_sum = node.value + left_sum + right_sum
            max_sum = max(max_sum, current_sum)

            return node.value + max(left_sum, right_sum)

        max_sum = float('-inf')
        max_path_sum_helper(root)

        return max_sum

# Create an instance of Solution
solution = Solution()

# Create a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)

# Check the maximum path sum
print(solution.max_path_sum(root))
# Output: 6

In this solution, we define a Node class to represent a node in the binary tree. We also define a Solution class that contains the max_path_sum method to find the maximum path sum in the binary tree.

The max_path_sum method uses a helper function max_path_sum_helper to recursively calculate the maximum path sum starting from each node. It computes the maximum sum from the left subtree, the maximum sum from the right subtree, and the current sum (node value + left sum + right sum). It updates the max_sum variable with the maximum of the current sum and the existing max_sum.

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 recursive calls consume stack space. In the worst case, when the tree is skewed, the height is O(n), resulting in O(n) space complexity.