Same Tree | Blind 75 | Leetcode question

What are some real world usage of this tree comparison algorithm?

1. Facebook: React's Virtual DOM:

• In React (built by Facebook), the UI is represented as a tree. During rendering, Facebook uses a concept similar to comparing two trees (old Virtual DOM vs. new Virtual DOM) to determine what changes need to be updated in the UI.
• This comparison ensures optimal rendering by minimizing updates.

2. Amazon: Merkle Trees in S3 and DynamoDB:

• Amazon uses Merkle Trees to ensure data consistency across its globally distributed storage systems (e.g., S3 buckets). The tree comparison ensures that replicated data is consistent between regions.

2. Google: Google Drive File Sync:

• Google Drive syncs hierarchical file trees between local and cloud storage. When a user uploads files, Google compares the local directory tree with the cloud tree to detect changes and synchronize the content.

Now that we understand what's the use of this algorithm. let's look into our actual question of comparing if two binary trees given to us are same or not.

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Derivatives:

1. Two trees are identical if all the nodes in tree are same.
2. We compare
3. root node
4. identical left subtree
5. identical right subtree
6. So we are sure we need a traversal algorithm
7. Breadth first search
8. Depth first search
9. Now let's try to pick which traversal algorithm to pick:

function bfs(root){
    /*
         we want a 
         1. currentNode
         2. list to store the result
         3. queue to process inorder

         next we check if we have data to process in the queue
          
         if(queue.length > 0){
            let node = queue.shift()
            list.push(node.value)
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
         }
         return list
    */

         const list = []
         const queue = []

        queue.push(root)
        while(queue.length > 0){
            let currentNode = queue.shift()
            list.push(currentNode.value)    

            currentNode.left && queue.push(currentNode.left)
            currentNode.right && queue.push(currentNode.right)
        }
        return list
}

How do we link this solution to check if the tree are identical?

1. Can we compare the length of the list result at the end?
2. Can we loop over each element in the list of 1 tree and compare the value at that position in another tree?

To me this sounds reasonable solution??

BFS ensures that the nodes are visited level by level. However, two trees can have the same BFS result but different structures. For example:

Tree 1:     Tree 2:
    1            1
   /              \
  2                2

Both trees would produce the same BFS result [1, 2], but they are structurally different.

So we need to account for:

1. Order of traversal.
2. Null Nodes in BFS
3. In a complete tree representation for BFS comparison, you would need to account for null nodes (e.g., missing left or right children). Otherwise, a sparse tree and a dense tree could produce the same list if you ignore null nodes.
4. Performance:
5. Generating two BFS lists and comparing them adds overhead compared to directly comparing the trees as we traverse them.

So does it have to do anything with BFS or DFS at all?

All we know is we need to traverse all the nodes in a tree and compare to each other as we traverse.

So do we need recursion? or iterative solution?

To me if we are solving same nature of problem over and over again it is some kind of recursive problem.

Does that ring a bell? Recursive is how our DFS are designed.

We want to compare these nodes as we go through: i.e grab as you go (Pre-order)

function dfsPreOrder(node){
    // list.push(node.value)
    dfsPreOrder(node.left)
    dfsPreOrder(node.right)
}

Now next few questions we need to tackle:

1. Are we going to process both tree the same time?
2. What is our base case?
3. if we hit null what happens?
4. if both hits null the same time? it is sameTree
5. else then it is not
6. If one tree hits null and another is still processing, we disqualify

function isSameTree(pTreeNode , qTreeNode){
    /*
        grab as you go
        base cases
        1. if both nodes are null, it's same return true
        2. if one nodes exist and other don't return false
        3. if at anypoint the nodes are not equal return false
    */

   if(!pTreeNode && !qTreeNode) return true
   if(!pTreeNode || !qTreeNode) return false
   if(pTreeNode.val !== qTreeNode.val) return false
    return isSameTree(pTreeNode.left, qTreeNode.left) && isSameTree(pTreeNode.right, qTreeNode.right)
}

Complexity:

1. Time Complexity:
2. O(N) as we are traversing each nodes in the tree
3. N represents the total number of nodes in the smaller of the two trees (if they differ in size).
4. Space Complexity:
5. O(H) as we are recursively going through nodes
6. The recursion stack can grow to a maximum depth equal to the height of the tree
7. For a balanced tree, the height is O(log⁡N), so the space complexity would reduce to O(log⁡N) in such cases.

Following up questions:

Algorithm and Approach

1. Why did you choose a recursive solution over an iterative one for this problem? Could you implement it iteratively?
2. Tests your ability to justify design decisions and explore alternative approaches.
3. What is the time complexity of your solution? Can it be optimized further?
4. Evaluates your understanding of performance.
5. What are the potential edge cases for this problem, and how does your solution handle them?
6. Checks if you considered scenarios like null nodes, single-node trees, or unbalanced trees.
7. Can you modify the function to return the number of differences between the two trees instead of just a boolean?

• Challenges you to adapt the algorithm for a slightly different requirement.

Data Structures

1. How would you handle this problem if the trees were not binary trees but N-ary trees?
2. Tests your ability to generalize the solution.
3. Can you use BFS instead of DFS to solve this problem? What would be the advantages or disadvantages?
4. Examines your grasp of different traversal strategies.

System Design and Real-World Applications

1. If the trees are very large and cannot fit into memory, how would you compare them?
2. Introduces constraints like memory limitations or streaming data.
3. In what real-world scenarios might you encounter a need to compare trees like this?
4. Probes your ability to connect the problem to practical use cases.

Extensions and Variations

1. How would you adapt your solution to check if one tree is a subtree of the other?
2. Tests your ability to extend the problem.
3. If instead of exact matching, we want to check if the trees are structurally identical but allow small differences in values, how would you modify the solution?
4. Introduces flexibility to the matching criteria.

let's continue the discussion!!

#blind75 #tree #binaryTree