Skip to main content

​
Overview

The UCX DSA package provides a complete binary search tree (BST) implementation through the Tree and TreeNode classes. A binary search tree is a hierarchical data structure where each node has at most two children, and for every node, all values in the left subtree are smaller and all values in the right subtree are larger.

​
Use Cases

Sorted Data

Maintain data in sorted order with efficient insertion and deletion

Fast Search

Search for values in O(log n) time on balanced trees

Range Queries

Find all values within a specific range efficiently

Priority Systems

Implement priority-based systems with ordered access

​
TreeNode Class

The TreeNode class represents a single node in a binary tree.

​
Constructor

from dsa.tree import TreeNode

# Create a node with a value
node = TreeNode(10)

# Create a node with children
left_child = TreeNode(5)
right_child = TreeNode(15)
parent = TreeNode(10, left=left_child, right=right_child)

​
Key Methods

Returns a deep copy of the node and all its descendants.
original = TreeNode(10, TreeNode(5), TreeNode(15))
duplicate = original.copy()

​
Tree Class (Binary Search Tree)

The Tree class implements a binary search tree with standard BST operations. It can also be used as a plain binary tree if you manually set nodes without using insert/search/delete operations.

​
Creating a Tree

from dsa.tree import Tree, TreeNode

# Create an empty tree
tree = Tree()

# Create a tree with an existing root
root = TreeNode(50)
tree = Tree(root)

​
Core Operations

1

Insert Values

Add values to the BST while maintaining the BST property.
tree = Tree()
tree.insert(50)
tree.insert(30)
tree.insert(70)
tree.insert(20)
tree.insert(40)
The insert() method uses recursion by default. For iterative insertion, use insert_iterative().
2

Search for Values

Find a node with a specific value.
try:
    node = tree.search(30)
    print(f"Found node: {node.value}")  # Output: Found node: 30
except ValueError:
    print("Value not found")
The search() method raises a ValueError if the value is not found.
3

Delete Values

Remove a node from the BST.
tree.delete(30)
# The tree automatically restructures to maintain BST properties
The deletion handles three cases:
  • Node with no children (leaf)
  • Node with one child
  • Node with two children (replaces with in-order successor)

​
Helper Methods

​
Finding Successor and Predecessor

# Find the minimum value in the right subtree
node = tree.successor_node(tree.root.right)
print(node.value)  # Smallest value in right subtree

​
Printing and Length

# Print the tree structure
tree.print()

# Get the number of nodes
count = len(tree)
print(f"Tree has {count} nodes")

​
Complete Example

from dsa.tree import Tree

# Create and populate a BST
tree = Tree()
values = [50, 30, 70, 20, 40, 60, 80]

for value in values:
    tree.insert(value)

print(f"Tree size: {len(tree)}")  # Output: Tree size: 7

# Search for a value
try:
    node = tree.search(40)
    print(f"Found: {node.value}")  # Output: Found: 40
except ValueError as e:
    print(e)

# Delete a value
tree.delete(30)
print(f"After deletion: {len(tree)}")  # Output: After deletion: 6

# Print the tree structure
tree.print()

​
Visualization

You can visualize trees using the TreeDraw class from the draw module: 
from dsa.tree import Tree
from dsa.draw import TreeDraw

# Create and populate a tree
tree = Tree()
for value in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(value)

# Visualize the tree
td = TreeDraw(tree)
td.draw()  # Display the tree

# Or save to a file
td.save("my_tree.png")
The visualization uses NetworkX and Matplotlib to create a hierarchical graph representation of the tree structure.

​
Comparison Operations

# TreeNode comparison
node1 = TreeNode(5)
node2 = TreeNode(10)
print(node1 < node2)  # Output: True

# Tree equality
tree1 = Tree()
tree2 = Tree()
for val in [50, 30, 70]:
    tree1.insert(val)
    tree2.insert(val)

print(tree1 == tree2)  # Output: True (same structure and values)

​
Time Complexity

OperationAverage CaseWorst Case
InsertO(log n)O(n)
SearchO(log n)O(n)
DeleteO(log n)O(n)
CopyO(n)O(n)
Worst case occurs when the tree becomes unbalanced (e.g., inserting sorted data). Consider using a self-balancing tree for guaranteed O(log n) operations.

​
API Reference

For detailed API documentation, see:

Build docs developers (and LLMs) love

Get started for freeTalk to us