Most DeFi protocols are reinventing the wheel with basic data structures.

Your AMM is doing O(n) liquidity queries when it could be O(log n), and your lending protocol is iterating through arrays when bitmaps exist. Your DEX is wasting 50k+ gas on operations that could cost 3k.

If your background isn't in computer science, and you are in the blockchain space, you might find it difficult to maintain your position in the industry, either as a Builder, Auditor, or Researcher, as more and more projects are adopting complex data structures to improve performance.

🔥 The gap is widening:

• Junior devs write loops, senior devs write trees

• Basic auditors check logic, elite auditors spot vulnerabilities

• Researchers who understand data structures predict the next breakthrough

As a Builder, Auditor, or Researcher post-2024, you can't afford to ignore data structures anymore.

I've compiled production-ready implementations of the data structures and a simple, understandable codebase that simplifies each of these protocols' data structures. This document explores the shift from traditional DeFi implementations to Tree and Graph-based architectures, highlighting their advantages, design patterns, and real-world applications through detailed case studies of live production protocols.

Understanding Trees and Graphs: The Foundation

Before diving into DeFi applications, let's establish a solid understanding of these fundamental data structures. Whether you're a seasoned developer or new to computer science, this section will provide the conceptual foundation needed to understand their revolutionary application in DeFi protocols.

What Are Trees?

A tree is a hierarchical data structure that organizes data in a parent-child relationship. Think of it like a family tree or an organizational chart - there's a clear hierarchy with one root at the top, and each element (called a "node") can have children below it.

Key Tree Characteristics

• Root: The topmost node (like a CEO in a company)

• Parent/Child: Each node can have children, and each child has exactly one parent

• Leaf: Nodes with no children (like employees with no direct reports)

• Depth: How many levels deep does the tree go

• Path: The route from one node to another

Visual Example:

        Root (CEO)
       /          \
   Manager A    Manager B
   /      \         |
John    Sarah    Alice

Types of Trees in DeFi

1. Binary Trees: Each node has at most 2 children (Manager A has John and Sarah)

2. Segment Trees: Specialized for range queries and updates

3. Merkle Trees: Used for cryptographic proofs (not covered in this doc)

What Are Graphs?

A graph is a more flexible structure consisting of vertices (nodes) connected by edges (connections). Unlike trees, graphs can have cycles and multiple paths between nodes. Think of it like a city road network - intersections (vertices) are connected by roads (edges), and you might reach the same destination through different route combinations.

Key Graph Characteristics

• Vertices (Nodes): The entities in the graph (intersections, tokens, pools)

• Edges: The connections between vertices (roads, swap pairs)

• Directed vs Undirected: Whether connections have direction (one-way vs two-way)

• Cycles: Circular paths (A connects to B, B to C, C back to A)

• Connected Components: Groups of vertices that can reach each other

Visual Example:

    Paris ---- Amsterdam ---- Madrid
    |             |             |
    |             |             |
    London ---- Berlin --------/

In this graph, you can travel from Paris to Madrid via multiple paths: Paris→Amsterdam→Madrid (direct, 2 hops), Paris→London→Berlin→Madrid (longer, 3 hops), or Paris→Amsterdam→Berlin→Madrid (alternative, 3 hops).

Trees vs Graphs: When to Use Which?

• Structure Differences: Trees maintain hierarchical organization without cycles, while graphs allow flexible connectivity with potential cycles and complex network relationships.

• Primary Use Cases: Trees are optimized for range queries and hierarchical data management, whereas graphs excel in network relationships and pathfinding scenarios.

• DeFi Applications: Trees handle price ranges and liquidity tiers effectively, while graphs manage token swap routing and pool connections across multiple assets.

• Implementation Complexity: Trees offer simpler traversal and implementation patterns, while graphs require more sophisticated algorithms but enable richer relationship modeling.

Why Traditional Arrays/Mappings Aren't Enough

In early DeFi (2020-2022), most protocols used simple data structures:

// Traditional approach - simple but inefficient
mapping(address => uint256) balances;  // O(1) lookup, but no relationships
uint256[] prices;                      // O(n) for range operations
mapping(uint256 => uint256) liquidityByTick; // O(n) for multi-tick updates

Problems with traditional approaches:

• Linear complexity: Updating multiple related items requires individual operations

• No relationships: Can't efficiently model connections between tokens/pools

• Gas inefficiency: Each operation costs gas; multiple operations cost multiple gas

• Limited queries: Hard to ask "what's the total liquidity in this price range?"

How Trees and Graphs Solve These Problems (you will write more code)

Trees Solve Range Operations:

// Tree approach - efficient range updates
function updateLiquidityRange(uint256 start, uint256 end, uint256 amount) {
    // O(log n) instead of O(n) - exponentially better!
    tree.updateRange(start, end, amount);
}

Graphs Solve Routing and Relationships:

// Graph approach - model complex token relationships
function findBestSwapPath(address tokenA, address tokenB) returns (address[] path) {
    // Can find optimal multi-hop routes through connected pools
    return graph.shortestPath(tokenA, tokenB);
}

The Evolution from Traditional to Tree-Based DeFi

Traditional DeFi Patterns (Pre-2023)

• Linear Array Storage: Most early AMMs used simple array-based liquidity tracking

• Hash Map Lookups: Price discovery through basic mapping structures

• Sequential Processing: Order matching and liquidity provision in linear time

• Gas Inefficiency: O(n) operations for price updates and range queries

Modern Patterns (2023-Present)

• Hierarchical Data Organization: Multi-level tree structures for efficient range queries

• Logarithmic Complexity: O(log n) operations for most critical functions

• Spatial Indexing: Tree-based tick and price range management

• Optimized Gas Usage: Batch operations and efficient traversal algorithms

Why Trees Matter in DeFi

1. Liquidity Range Management

Modern concentrated liquidity protocols need to:

• Efficiently find active liquidity at specific price points

• Update multiple price ranges simultaneously

• Handle range overlaps and merging

Traditional Approach:

// O(n) complexity for range updates
mapping(uint256 => uint256) liquidityByTick;
function updateLiquidity(uint256[] memory ticks, uint256[] memory amounts) {
    for (uint i = 0; i < ticks.length; i++) {
        liquidityByTick[ticks[i]] += amounts[i];
    }
}

Tree-Based Approach:

// O(log n) complexity using tree structure
function updateLiquidityRange(uint256 lowerTick, uint256 upperTick, uint256 amount) {
    tree.updateRange(lowerTick, upperTick, amount);
}

Tree Design Patterns in Production DeFi

As I journeyed through various DeFi protocols during development, audits, and research, I discovered several innovative tree and graph-based design patterns that have been successfully implemented in production environments. Here are some notable examples:

Burve Protocol Graph-Based System

System Overview

The Burve protocol, written as a Diamond pattern, implements a graph-based liquidity pool system. When you think of Graph, you think of nodes (Vertices) connected (Edges) and finding the shortest path between them, which is a key aspect in terms of developing Graph Algorithms in solidity, especially when it comes to optimizing gas costs and ensuring efficient data retrieval. Unlike trees, a graph is not hierarchical but a collection of nodes and edges, so a vertice can connect to multiple edges and form complex relationships.

• Vertices represent tokens/assets (You can call it nodes- (tokens, vaults, reserves))

• Closures represent groups of tokens (vertices) that can be swapped with each other (subgraphs). Think of it like a subgraph within the larger graph structure, where all tokens (Vertices) in the closure are interconnected and can be swapped directly with one another.

• Value Tokens represent shares in the overall liquidity system (you can think of it as a representation of the value of the assets in the system)

• Edges are implicitly defined by closures (tokens in the same closure can be swapped). You can think of it as the connections between nodes in a graph.

Basic Burve Graph Structure

How Swapping Works

Simple Example: ETH → DAI Swap

While this is similar to how you set path in Uniswap, the key difference is that in Burve, you don't have to deploy multiple pools of contracts; tokens are grouped into closures (Nodes), and swaps can only occur directly between tokens within the same closure(Node). If two tokens are not in the same closure (Node), a multi-hop swap through bridge tokens (tokens that exist in multiple closures (Nodes) is required. Unlike when a pool can only have 1 pair of tokens, in Burve, each closure (Node) can contain multiple tokens, allowing for more complex swap paths and better liquidity distribution, and you only have to pay fees for the closures you use.

Simple implementation: Optimal Design

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract BurveGraphSimplified {
    // Core graph structures
    struct Vertex {
        uint256 id;
        address tokenAddress;
        string tokenType; // "token", "vault", "reserve"
        uint256 balance;
    }
    
    struct Closure {
        uint256 id;
        string name;
        uint256[] vertexIds; // Vertices in this closure
        bool active;
    }
    
    // Global mappings (like actual Burve)
    mapping(uint256 => Vertex) public vertices;
    mapping(uint256 => Closure) public closures;
    mapping(uint256 => mapping(uint256 => bool)) public vertexInClosure;
    
    uint256 public nextVertexId = 1;
    uint256 public nextClosureId = 1;
    
    // Create a new closure (protocol function, not user)
    function createClosure(string memory _name) external returns (uint256) {
        uint256 closureId = nextClosureId++;
        closures[closureId] = Closure(closureId, _name, new uint256Unsupported embed, true);
        return closureId;
    }
    
    // Add vertex to system
    function addVertex(address _tokenAddress, string memory _tokenType) external returns (uint256) {
        uint256 vertexId = nextVertexId++;
        vertices[vertexId] = Vertex(vertexId, _tokenAddress, _tokenType, 0);
        return vertexId;
    }
    
    // Add vertex to closure (creates implicit edges)
    function addVertexToClosure(uint256 _vertexId, uint256 _closureId) external {
        require(vertices[_vertexId].id != 0, "Vertex doesn't exist");
        require(closures[_closureId].id != 0, "Closure doesn't exist");
        
        closures[_closureId].vertexIds.push(_vertexId);
        vertexInClosure[_vertexId][_closureId] = true;
    }
    
    // Check if two vertices can swap directly (same closure)
    function canSwapDirect(uint256 _fromVertex, uint256 _toVertex) external view returns (bool) {
        // Check if both vertices exist in the same closure
        for (uint256 i = 1; i < nextClosureId; i++) {
            if (vertexInClosure[_fromVertex][i] && vertexInClosure[_toVertex][i]) {
                return true;
            }
        }
        return false;
    }
    
    // Find swap path (simplified)
    function findSwapPath(uint256 _fromVertex, uint256 _toVertex) 
        external view returns (uint256[] memory path) {
        // Simplified: find common closure or bridge vertex
        // In real implementation, this would use graph algorithms
    }
}

This is the basic structure of how the graph is represented in Burve and how swaps are facilitated through closures. The actual implementation would be more complex, especially in terms of pathfinding and optimizing for gas costs, but this gives a foundational understanding of the graph-based approach in the Burve protocol.

Ammplify Protocol Binary Tree System

System Overview

The Ammplify protocol implements a binary tree-based liquidity management system built as a Diamond proxy pattern. Unlike traditional AMMs that process liquidity linearly tick-by-tick, Ammplify organizes price ranges into a hierarchical binary tree structure that enables efficient range operations and dramatic gas optimizations.

To give a short illustration of what Binary Tree is: When you think of Binary Tree, you think of a hierarchical structure where each node has at most two children (left and right), unlike graphs where nodes can connect to multiple other nodes. In trees, there's exactly one path between any two nodes, and there's a clear parent-child relationship with a single root at the top. Let me not bore you with Tree explanation. In Ammplify, the binary tree consists of:

• Nodes represent price ranges (ticks) with different granularities - each covering a specific width of price space

• Keys uniquely identify each node using base + width encoding packed into 48-bit values

• Routes define optimal paths through the tree for range operations (like updating liquidity from tick 100 to 200)

• Walkers traverse the tree to update liquidity and balances using the calculated routes

• LCA (Lowest Common Ancestor) optimizes tree traversal by finding the smallest subtree containing the target range

Basic Binary Tree Structure

How Range Updates Work

Simple Example: Add Liquidity to Range [4, 7]

While this is similar to how you might update multiple ticks in Uniswap, the key difference is that in Ammplify, liquidity operations are organized into a tree structure where range updates follow optimal paths through the tree hierarchy. Unlike when you have to update each tick individually, in Ammplify, the tree walker finds the Lowest Common Ancestor (LCA) that covers your range and efficiently updates only the necessary nodes, allowing for logarithmic complexity instead of linear operations, and you only pay gas for the nodes you actually modify.

Simple implementation: Optimal Design

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract AmmplifyTreeSimplified {
    struct TreeNode {
        uint24 base;        // Starting tick
        uint24 width;       // Range width (power of 2)
        uint128 liquidity;  // Liquidity at this node
        uint128 subtreeLiq; // Total liquidity in subtree
    }
    
    // Tree storage: Key (base, width) -> Node data
    mapping(uint48 => TreeNode) public nodes;
    uint24 public rootWidth;
    
    // Initialize the tree with a root width (must be power of 2)
    constructor(uint24 _rootWidth) {
        require(_rootWidth > 0 && (_rootWidth & (_rootWidth - 1)) == 0, "Root width must be power of 2");
        rootWidth = _rootWidth;
    }
    
    // Create tree key from base and width
    function makeKey(uint24 base, uint24 width) public pure returns (uint48) {
        return (uint48(width) << 24) | base;
    }
    
    // Add liquidity to a range [left, right]
    function addLiquidity(uint24 left, uint24 right, uint128 amount) external {
        require(left <= right, "Invalid range");
        require(right < rootWidth, "Range exceeds tree bounds");
        
        // Use simplified iterative approach
        _updateRange(left, right, amount);
    }
    
    // ITERATIVE tree walking (simplified Ammplify LCA approach)
    function _updateRange(uint24 left, uint24 right, uint128 amount) internal {
        // 1. Find LCA that contains the range (like real Ammplify)
        uint24 lcaWidth = findLCAWidth(left, right);
        uint24 lcaBase = left & ~(lcaWidth - 1);
        
        // 2. Walk down from root to LCA, updating subtree totals
        uint24 currentBase = 0;
        uint24 currentWidth = rootWidth;
        
        while (currentWidth > lcaWidth) {
            uint48 key = makeKey(currentBase, currentWidth);
            nodes[key].subtreeLiq += amount * lcaWidth;  // Width-weighted like Ammplify
            
            // Navigate toward LCA
            uint24 midPoint = currentBase + currentWidth / 2;
            if (lcaBase < midPoint) {
                currentWidth /= 2;  // Go left
            } else {
                currentBase = midPoint;  // Go right
                currentWidth /= 2;
            }
        }
        
        // 3. Update the LCA node itself
        uint48 lcaKey = makeKey(lcaBase, lcaWidth);
        nodes[lcaKey].subtreeLiq += amount * lcaWidth;
        
        // 4. If LCA exactly matches our range, add direct liquidity
        if (lcaBase == left && (lcaBase + lcaWidth - 1) == right) {
            nodes[lcaKey].liquidity += amount;
        } else {
            // 5. Otherwise, recursively update children (simplified)
            _updateLCAChildren(lcaBase, lcaWidth, left, right, amount);
        }
    }
    
    // Handle range updates within the LCA subtree
    function _updateLCAChildren(uint24 base, uint24 width, uint24 left, uint24 right, uint128 amount) internal {
        if (width == 1) {
            // Leaf node - add direct liquidity
            uint48 key = makeKey(base, width);
            nodes[key].liquidity += amount;
            return;
        }
        
        uint24 midPoint = base + width / 2;
        uint24 leftWidth = width / 2;
        uint24 rightWidth = width / 2;
        
        // Update left child if range overlaps
        if (left < midPoint) {
            uint48 leftKey = makeKey(base, leftWidth);
            uint24 leftEnd = min(right, midPoint - 1);
            uint24 childAmount = (leftEnd - left + 1);
            nodes[leftKey].subtreeLiq += childAmount * amount;
            
            if (base == left && (base + leftWidth - 1) == leftEnd) {
                nodes[leftKey].liquidity += amount;
            } else if (leftWidth > 1) {
                _updateLCAChildren(base, leftWidth, left, leftEnd, amount);
            }
        }
        
        // Update right child if range overlaps  
        if (right >= midPoint) {
            uint48 rightKey = makeKey(midPoint, rightWidth);
            uint24 rightStart = max(left, midPoint);
            uint24 childAmount = (right - rightStart + 1);
            nodes[rightKey].subtreeLiq += childAmount * amount;
            
            if (midPoint == rightStart && (midPoint + rightWidth - 1) == right) {
                nodes[rightKey].liquidity += amount;
            } else if (rightWidth > 1) {
                _updateLCAChildren(midPoint, rightWidth, rightStart, right, amount);
            }
        }
    }
    
    // Query liquidity at a specific tick
    function getLiquidityAt(uint24 tick) external view returns (uint128 totalLiq) {
        require(tick < rootWidth, "Tick out of bounds");
        
        // Walk down tree to accumulate liquidity
        uint24 currentBase = 0;
        uint24 currentWidth = rootWidth;
        
        while (currentWidth >= 1) {
            uint48 key = makeKey(currentBase, currentWidth);
            totalLiq += nodes[key].liquidity;
            
            if (currentWidth == 1) break;
            
            // Navigate to appropriate child
            uint24 midPoint = currentBase + currentWidth / 2;
            if (tick < midPoint) {
                currentWidth /= 2;
            } else {
                currentBase = midPoint;
                currentWidth /= 2;
            }
        }
    }
    
    // Get node data at specific base and width
    function getNode(uint24 base, uint24 width) public view returns (TreeNode memory) {
        uint48 key = makeKey(base, width);
        return nodes[key];
    }
    
    // Helper function for testing - get root node
    function getRootNode() external view returns (TreeNode memory) {
        return getNode(0, rootWidth);
    }
    
    function findLCAWidth(uint24 left, uint24 right) internal pure returns (uint24) {
        if (left == right) return 1;
        uint24 diff = left ^ right;
        return msb(diff) << 1; // Next power of 2
    }
    
    function min(uint24 a, uint24 b) internal pure returns (uint24) {
        return a < b ? a : b;
    }
    
    function max(uint24 a, uint24 b) internal pure returns (uint24) {
        return a > b ? a : b;
    }
    
    // Simple MSB function for demonstration
    function msb(uint24 x) internal pure returns (uint24 r) {
        if (x >= 0x100) { x >>= 8; r += 8; }
        if (x >= 0x10) { x >>= 4; r += 4; }
        if (x >= 0x4) { x >>= 2; r += 2; }
        if (x >= 0x2) r += 1;
    }
}

This is the basic structure of how the binary tree is represented in Ammplify and how range updates are facilitated through tree traversal. The actual implementation would be more complex, especially in terms of fee calculations and maker/taker interactions, but this gives a foundational understanding of the tree-based approach in the Ammplify protocol.

Real-World Usage

In production, Ammplify uses this tree system for:

1. Maker Operations: Adding/removing liquidity ranges efficiently

2. Taker Operations: Borrowing liquidity against collateral

3. Fee Distribution: Proportional fee sharing across tree nodes

4. Price Discovery: Fast lookups for active liquidity at cthe urrent price

5. Rebalancing: Moving liquidity between price ranges with minimal gas

This binary tree architecture represents a fundamental evolution in AMM design, moving from linear tick processing to hierarchical range management, enabling new possibilities for capital efficiency and gas optimization in DeFi.