Solving a LeetCode problem with Blockchain concept 😎

Published in

Coinmonks

4 min readDec 23, 2022

I am just amazed to see that an Easy Leetcode problem can teach us a concept which is used in BlockChain for decentralization🤯. Let us wear the magic glasses giving us different perspective to view this question!

A sneak-peek to the concept 🤫: We will be using Merkle Trees

⁕ The Problem:

https://leetcode.com/problems/subtree-of-another-tree

⁕ General approach :

The Naive approach is to simply have a function isSameTree and run this recursively for to check if their roots match along with the subtree! Well, not going deeper into this explanation as this is not the aim of this article.

New to trading? Try crypto trading bots or copy trading on best crypto exchanges

If you wish to learn this, here’s the code:

 
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL || q == NULL) return (p == q);
        if(p->val != q->val) return false;
        
        return (isSameTree(p->left, q->left) && 
                isSameTree(p->right, q->right));
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(isSameTree(root, subRoot)) 
            return true;
        if(! root) 
            return false;
        
        return (isSubtree(root->left, subRoot) ||
                isSubtree(root->right, subRoot));
    }

⁕ The approach which teaches the concept used in BlockChain 💙

Drumrolls 🥁🥁🥁

The concept we will be using here is Merkle Trees.

⁕ Diving deeper into the concept of Merkle Tree

Merkle tree or hash tree is a tree structure in which leaf node contains the cryptographic hash of the block of data and non-leaf node contains cryptographic hash of its children.
In Bitcoin and other cryptocurrencies, a Merkle tree database is used to securely split the block’s data and ensure that it is not lost, damaged, or altered, basically to encrypt data more securely.
Each and every node on the network would have been required to maintain a complete copy of all the transactions that has ever taken place on the blockchain if Merkle trees were not existing!!!
Every node would have had to compare each entry line by line when verifying a transaction to ensure that its records exactly match the network records and this would have required enormous amount of computational power!!

Now that we have known basics of Merkle tree, that we can identify all the transactions of the child nodes as well from the hash of root of merkle tree, let us use the same concept in the Leetcode problem!

⁕ Solving leetcode problem with merkle trees:

So, for each node of the tree we create merkle which is hash of its children or subtree.
In blockchain, generally hash SHA256 is used which is a cryptographic hash. Checkout more about it here.
It is the concatenation of merkle of left subtree + root’s value + merkle of right subtree!
Once we have formed merkle of every root, we can simply traverse and check if the merkle of root of tree is matching the merkle of root of subtree.
This is the python code from discuss tab, implemented by importing sha256.

def isSubtree(self, s, t):
    from hashlib import sha256
    def hash_(x):
        S = sha256()
        S.update(x)
        return S.hexdigest()
        
    def merkle(node):
        if not node:
            return '#'
        m_left = merkle(node.left)
        m_right = merkle(node.right)
        node.merkle = hash_(m_left + str(node.val) + m_right)
        return node.merkle
        
    merkle(s)
    merkle(t)
    def dfs(node):
        if not node:
            return False
        return (node.merkle == t.merkle or 
                dfs(node.left) or dfs(node.right))
                    
    return dfs(s)