BST

BST.sol

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.15;

contract BinaryTree2 {
    struct Node {
        uint256 value;
        int256 height;
        bytes32 left;
        bytes32 right;
    }
    
    mapping (bytes32 => Node) public tree;
    bytes32 public rootAddress;
    mapping (uint256 => bytes32) public bytesmap;
    uint256 public count;
    uint256 public flagcheck;
    bytes32 public zerobytes = 0x0000000000000000000000000000000000000000000000000000000000000000;
    uint[] public values1;
    uint[] public values2;
    uint[] public values3;
    bytes32 public checkBytes;
    int256 public height1;

    constructor() {
        rootAddress = bytes32(0);
    }

    // helper function to generate an ID
    function generateId(uint256 value, bytes32 parentAddress) public view returns (bytes32) {
        // generate a unique id for the node
        return keccak256(
            abi.encodePacked(
                value,
                parentAddress,
                block.timestamp
            )
        );
    }

    function createNode(
        uint256 _value,
        int256 _height,
        bytes32 _left,
        bytes32 _right
    ) internal returns (Node memory node) {
        node = Node({
            value: _value,
            height: _height,
            left: _left,
            right: _right
        });
    }

    function isEmpty() public returns(bool){
        return rootAddress == bytes32(0);
    }
 
    function clear() public {
        rootAddress = bytes32(0);
    }
 
    function insert(uint256 data) public {
        rootAddress = insert(data, rootAddress);
    }

    function height(bytes32 root) public returns(int256) {
        return root == bytes32(0) ? -1 : tree[root].height;
    }

    function max(int256 lhs, int256 rhs) public returns(int256) {
        return lhs > rhs ? lhs : rhs;
    }

    function setFlagcheck() public {
        flagcheck = 0;
    }
 
    function insert(uint256 x, bytes32 root) 
        public 
        returns(bytes32)
    {
        Node memory t = tree[root];
        bytes32 nodeId;
        if (root == zerobytes) {
            Node memory t1 = createNode(x, 0, bytes32(0), bytes32(0));
            nodeId = generateId(x, root);
            tree[nodeId] = t1;

            count++;
            bytesmap[count] = nodeId;

            if (rootAddress == zerobytes) {
                flagcheck = 1;
                rootAddress = nodeId;
                root = rootAddress;
            } else {
                flagcheck = 2;
                root = nodeId;
            }

        } else if (x < t.value) {
            flagcheck += 100;
            nodeId = insert(x, t.left);
            t.left = nodeId;
            // t.left = insert(x, t.left);
            if (height(t.left) - height(t.right) == 2){
                if (x < tree[t.left].value) {
                    t = rotateWithLeftChild(root);
                } else {
                    t = doubleWithLeftChild(root);
                }
                // root = nodeId;
            }
            tree[root] = t;
        } 
        else if (x > t.value) {
            flagcheck += 200;
            nodeId = insert(x, t.right);
            t.right = nodeId;
            // t.right = insert(x, t.right);
            if (height(t.right) - height(t.left) == 2) {
                if (x > tree[t.right].value) {
                    t = rotateWithRightChild(root);
                } else {
                    t = doubleWithRightChild(root);
                }
                // root = nodeId;
            } 
            tree[root] = t;
        }

        tree[root].height = max(
            height(tree[root].left), 
            height(tree[root].right)
        ) + 1;

        // return t;
        checkBytes = root;
        return root;
    }

    function rotateWithLeftChild(
        // Node memory t
        bytes32 nodeId
    ) public returns (Node memory) {
        Node memory k2 = tree[nodeId];
        Node memory k1 = tree[k2.left];

        // Node memory k2 = t;
        // Node memory k1 = tree[k2.left];

        k2.left = k1.right;
        k1.right = nodeId; // nodeId of k2

        k2.height = max(height(k2.left), height(k2.right)) + 1;
        k1.height = max(height(k1.left), k2.height) + 1;
        return k1;
        // return k2.left;
    }
 
    function rotateWithRightChild(
        // Node memory t
        bytes32 nodeId
    ) public returns (Node memory) {
        Node memory k1 = tree[nodeId];
        Node memory k2 = tree[k1.right];

        // Node memory k1 = t;
        // Node memory k2 = tree[k1.right];

        k1.right = k2.left;
        k2.left = nodeId; // nodeId of k2
        k1.height = max(height(k1.left), height(k1.right)) + 1;
        k2.height = max(height(k2.right), k1.height) + 1;
        return k2;
        // return k1.right;
    }
 
    function doubleWithLeftChild(bytes32 nodeIdOfK3) public returns (Node memory) {
        tree[tree[nodeIdOfK3].left] = rotateWithRightChild(tree[nodeIdOfK3].left);
        return rotateWithLeftChild(nodeIdOfK3);
    }
 
    function doubleWithRightChild(bytes32 nodeIdOfK1) public returns (Node memory) {
        tree[tree[nodeIdOfK1].right] = rotateWithLeftChild(tree[nodeIdOfK1].right);
        return rotateWithRightChild(nodeIdOfK1);
    }
    
    function inorder(bytes32 root) public returns(uint256[] memory) {
        if (root != bytes32(0)) {
            inorder(tree[root].left);
            values1.push(tree[root].value);
            inorder(tree[root].right);
        }
        return values1;
    }

    function preorder(bytes32 root) public returns(uint256[] memory) {
        if (root != bytes32(0)) {
            values2.push(tree[root].value);
            preorder(tree[root].left);
            preorder(tree[root].right);
        }
        return values2;
    }

    function postorder(bytes32 root) public returns(uint256[] memory) {
        if (root != bytes32(0)) {
            postorder(tree[root].left);
            postorder(tree[root].right);
            values3.push(tree[root].value);
        }
        return values3;
    }
}

gistfile1.txt

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.15;

contract BinaryTree2 {
    struct Node {
        uint256 value;
        int256 height;
        bytes32 left;
        bytes32 right;
    }
    
    mapping (bytes32 => Node) public tree;
    bytes32 public rootAddress;
    mapping (uint256 => bytes32) public bytesmap;
    uint256 public count;
    uint256 public flagcheck;
    bytes32 public zerobytes = 0x0000000000000000000000000000000000000000000000000000000000000000;
    uint[] public values1;
    uint[] public values2;
    uint[] public values3;
    bytes32 public checkBytes;
    int256 public height1;

    constructor() {
        rootAddress = bytes32(0);
    }

    // helper function to generate an ID
    function generateId(uint256 value, bytes32 parentAddress) public view returns (bytes32) {
        // generate a unique id for the node
        return keccak256(
            abi.encodePacked(
                value,
                parentAddress,
                block.timestamp
            )
        );
    }

    function createNode(
        uint256 _value,
        int256 _height,
        bytes32 _left,
        bytes32 _right
    ) internal returns (Node memory node) {
        node = Node({
            value: _value,
            height: _height,
            left: _left,
            right: _right
        });
    }

    function isEmpty() public returns(bool){
        return rootAddress == bytes32(0);
    }
 
    function clear() public {
        rootAddress = bytes32(0);
    }
 
    function insert(uint256 data) public {
        rootAddress = insert(data, rootAddress);
    }

    function height(bytes32 root) public returns(int256) {
        return root == bytes32(0) ? -1 : tree[root].height;
    }

    function max(int256 lhs, int256 rhs) public returns(int256) {
        return lhs > rhs ? lhs : rhs;
    }

    function setFlagcheck() public {
        flagcheck = 0;
    }
 
    function insert(uint256 x, bytes32 root) 
        public 
        returns(bytes32)
    {
        Node memory t = tree[root];
        bytes32 nodeId;
        if (root == zerobytes) {

            t = createNode(x, 0, bytes32(0), bytes32(0));
            nodeId = generateId(x, root);
            tree[nodeId] = t;
            checkBytes = nodeId;

            count++;
            bytesmap[count] = nodeId;

            if (rootAddress == zerobytes) {
                flagcheck += 1;
                rootAddress = nodeId;
                root = rootAddress;
            } else {
                root = nodeId;
            }
            
        } else if (x < t.value) {
            nodeId = insert(x, t.left);
            t.left = nodeId;
            if (height(t.left) - height(t.right) == 2){
                if (x < tree[t.left].value) {
                    flagcheck += 500;
                    t = rotateWithLeftChild(root);
                } else {
                    flagcheck += 10000;
                    t = doubleWithLeftChild(root);
                }
                // root = nodeId;
            }
            // tree[root] = t;
        } 
        else if (x > t.value) {
            nodeId = insert(x, t.right);
            t.right = nodeId;
            if (height(t.right) - height(t.left) == 2) {
                if (x > tree[t.right].value) {
                    flagcheck += 50000;
                    t = rotateWithRightChild(root);
                } else {
                    flagcheck += 1000;
                    t = doubleWithRightChild(root);
                }
                // root = nodeId;
            }
            // tree[root] = t;
        }

        t.height = max(
            height(t.left), 
            height(t.right)
        ) + 1;
        tree[root] = t;
        return root;
    }

    function rotateWithLeftChild(
        bytes32 nodeId
    ) public returns (Node memory) {
        Node memory k2 = tree[nodeId];
        Node memory k1 = tree[k2.left];
        k2.left = k1.right;
        k1.right = nodeId; // nodeId of k2
        k2.height = max(height(k2.left), height(k2.right)) + 1;
        k1.height = max(height(k1.left), k2.height) + 1;
        return k1;
    }
 
    function rotateWithRightChild(
        bytes32 nodeId
    ) public returns (Node memory) {
        Node memory k1 = tree[nodeId];
        Node memory k2 = tree[k1.right];
        k1.right = k2.left;
        k2.left = nodeId; // nodeId of k2
        k1.height = max(height(k1.left), height(k1.right)) + 1;
        k2.height = max(height(k2.right), k1.height) + 1;
        return k2;
    }
 
    function doubleWithLeftChild(bytes32 nodeIdOfk3) public returns (Node memory) {
        // Node memory k3 = tree[nodeIdOfK3];
        // tree[tree[nodeIdOfK3].left] = rotateWithRightChild(tree[nodeIdOfK3].left);
        // k3.left = rotateWithRightChild(k3.left);
        // return rotateWithLeftChild(nodeIdOfK3);

        Node memory k3 = tree[nodeIdOfk3];
        bytes32 tempK3Left = k3.left;
        Node memory k1 = tree[k3.left];

        // pass k1 to rotateWithRightChild;
        Node memory k2 = tree[k1.right];
        bytes32 tempK2 = k1.right;
        k1.right = k2.left;
        k2.left = tempK3Left; // nodeId of k2
        k1.height = max(height(k1.left), height(k1.right)) + 1;
        k2.height = max(height(k2.right), k1.height) + 1;

        k3.left = tempK2; // update k3 and pass to rotateWithLeftChild
        Node memory k11 = tree[k3.left];
        k3.left = k11.right;
        k11.right = tempK2;
        k3.height = max(height(k3.left), height(k3.right)) + 1;
        k11.height = max(height(k11.left), k3.height) + 1;
        return k11;
    }
 
    function doubleWithRightChild(bytes32 nodeIdOfK1) public returns (Node memory) {
        // tree[tree[nodeIdOfK1].right] = rotateWithLeftChild(tree[nodeIdOfK1].right);
        // return rotateWithRightChild(nodeIdOfK1);

        Node memory k1 = tree[nodeIdOfK1];
        bytes32 tempK1Right = k1.right;
        Node memory k2 = tree[k1.right];

        // rotateWithLeftChild
        Node memory k11 = tree[k2.left];
        bytes32 tempK11 = k2.left;
        k2.left = k11.right;
        k11.right = tempK1Right;
        k2.height = max(height(k2.left), height(k2.right)) + 1;
        k11.height = max(height(k11.left), k2.height) + 1;
        // return k1;

        k1.right = tempK11; // update k3 and pass to rotateWithLeftChild
        Node memory k22 = tree[k1.right];
        k1.right = k22.left;
        k22.left = tempK1Right;
        k1.height = max(height(k1.left), height(k1.right)) + 1;
        k22.height = max(height(k22.right), k1.height) + 1;
        return k22;
    }
    
    function inorder(bytes32 root) public returns(uint256[] memory) {
        if (root != bytes32(0)) {
            inorder(tree[root].left);
            values1.push(tree[root].value);
            inorder(tree[root].right);
        }
        return values1;
    }

    function preorder(bytes32 root) public returns(uint256[] memory) {
        if (root != bytes32(0)) {
            values2.push(tree[root].value);
            preorder(tree[root].left);
            preorder(tree[root].right);
        }
        return values2;
    }

    function postorder(bytes32 root) public returns(uint256[] memory) {
        if (root != bytes32(0)) {
            postorder(tree[root].left);
            postorder(tree[root].right);
            values3.push(tree[root].value);
        }
        return values3;
    }
}
// Self Balancing Tree
 
// 45
// 46
// 48
// 98
// 23
// 34
// 65
// 59
// 21
// 10
 

// In-order   :
// 10 21 23 34 45 46 48 59 65 98 
// Pre-order  :
// 46 34 21 10 23 45 65 48 59 98 
// Post-order :
// 10 23 21 45 34 59 48 98 65 46