Day 18 of 30 days of Data Structures and Algorithms and System Design Simplified — Trees
Welcome back peeps. Hope all’s well. In this post we will cover Trees as follows —
What and Why Trees(in 2–3 sentences)?
How does Tree work?
Important Patterns and Techniques in Trees Questions
Most Important Questions with Solutions
Tips and Techniques to solve Trees Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Complete Data Structures and Algorithm Series
Github —
Trees
Importance : Very High
Note : New Trees questions with solutions are added every day. So keep checking this post daily.
Let’s dive in!
What is a Tree?
Tree is one of the most important non-linear data structure which is hierarchical in nature — consists of nodes which are connected by the edges.
The first node is called the root. The last node is/are the leaf nodes and at every level a child node can have a sibling node( on left or right subtree).
Edge is the connection between one node to another node. Siblings aee the nodes with the same parent. Traversing or a path is the no of edges between respective nodes.
Data access is quicker and easier when it comes to trees ( non linear data structure)
Examples of Trees problems —
Max depth of a tree
Diameter of a tree
Invert a tree
Flip a tree
Inorder/Preorder/Postorder Tree Traversals etc
How does Trees work?
A tree works by having a root node, and each node in the tree can have multiple children nodes, and each child node can also have multiple children nodes and so on. This creates a hierarchical relationship between the nodes in the tree. The tree can be traversed by starting from the root node, and visiting each child node recursively.
There are (mainly) two types of trees ( under the scope of this post)
Binary Tree — It’s a non linear tree data structure with the possibility of having at the most two children for each node.
Binary Search Tree — It’s a variant of binary tree with nodes following the property : left child contains nodes with values less than the parent node and the right child nodes only contains nodes with values greater than the parent node. And lastly there should not be any duplicate nodes.
Tree Traversal
In order to perform any operation on a tree, you need to reach to the specific node.
Inorder Traversal — Visit the root node then visit all the nodes in left subtree and lastly visit all the nodes in right subtree
Pre-order Traversal — Visit all the nodes in left subtree then Visit the root node and lastly visit all the nodes in right subtree
Postorder Traversal — Visit all the nodes in left subtree then visit all the nodes in right subtree and lastly visit all the root node.
Important Patterns and Techniques in Trees Questions
Important patterns and techniques in Trees questions include understanding tree traversals such as DFS and BFS, identifying the root node, identifying the parent-child relationship, and recognizing the appropriate time to use Tree data structure.
Depth of a node is the number of edges from the root to the node.
height of a Tree is the height of the root node or the depth of the deepest node
Level of node is the rank i.e to which generation/rank it belong.
Degree of node is the total no of children it has.
Subtree is the descendants of the main tree.
Patterns → Questions like below belong to Trees( not limited to):
Traversal questions
Sorted Array to Tree
Max depth of a tree
Diameter of a tree
Invert a tree
Flip a tree etc
Most Important Questions with Solutions
Note : New Trees questions with solutions are added every day. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Trees questions.
Same Tree
Question —
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.
Example :
Input: p = [1,2,3], q = [1,2,3]
Output: trueSolution :
Main Logic/Idea —
The main logic is to recursively check if the left subtree is same tree and same goes for the right subtree. To check if they are same or not then check the corresponding nodes value and the structure ( sides).
Implementation —
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if not p or not q or p.val != q.val :
return False
return (self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right))Question Link
Similar Pattern —
Count Nodes Equal to Average of Subtree
Delete Leaves With a Given Value
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Invert Binary Tree
Question —
Given the root of a binary tree, invert the tree, and return its root.
Example :
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]Solution :
Main Logic/Idea —
The main logic — to invert left tree ( by calling invertTree function recursively) on the left tree. Invert right tree( by calling invertTree function recursively) on the right tree. Assign the right to left and vice versa.
Implementation —
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
temp = root.left
root.left = root.right
root.right = temp
self.invertTree(root.left)
self.invertTree(root.right)
return rootQuestion Link
Similar Pattern —
Reverse Odd Levels of Binary Tree
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Flip Equivalent Binary Trees
Question —
For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.
A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.
Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.
Example :
Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: trueSolution :
Main Logic/Idea —
The main gist is — Flip the left and right subtree, flip the roots ( right and left) recursively. If the trees node/root value is not equal then return False.
Implementation —
def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if not root1 or not root2:
return not root1 and not root2
if root1.val != root2.val:
return False
ans = (self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right)) or (self.flipEquiv(root1.left,root2.right) and self.flipEquiv(root1.right,root2.left))
return ansQuestion Link
Similar Pattern —
Smallest String Starting From Leaf
Delete Leaves With a Given Value
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Binary Tree Inorder Traversal
Question —
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: root = [1,null,2,3]
Output: [1,3,2]Solution :
Main Logic/Idea —
The main logic is to follow Inorder traversal rule — Left, Root, Right.
So first traverse the left subtree, then root and then right subtree.
Implementation —
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
def ino(root):
if not root:
return
ino(root.left)
ans.append(root.val)
ino(root.right)
ino(root)
return ansQuestion Link
Similar Pattern —
Convert Binary Search Tree to Sorted Doubly Linked List
Minimum Distance Between BST Nodes
Closest Binary Search Tree Value II
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Maximum Depth of Binary Tree
Question —
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example :
Input: root = [3,9,20,null,null,15,7]
Output: 3Solution :
Main Logic/Idea —
The main idea is to calculate the depth of left subtree and right subtree and then choose whichever is max ( add 1 to it).
Implementation —
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root: return 0
return 1+ max((self.maxDepth(root.left)), (self.maxDepth(root.right)))Question Link
Similar Pattern —
Time Needed to Inform All Employees
Amount of Time for Binary Tree to Be Infected
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Tree Questions with solutions will be added everyday. So keep checking this post daily.
Complexity Analysis
First go thorough complexity analysis post before reading this section of the post.
For Binary Search Tree —
Access — O(logn)
Search — O(logn)
Insertion — O(logn)
Deletion — O(logn)
Tips and Techniques to solve Trees Questions Fast.
Before solving the tree questions, remember below points —
- You should know Tree traversals on your finger tips.
- Know the properties of binary search tree well.
- Sorted array — tree questions point to BST
- Know recursion well.
That’s it for now. Day 19 : Graph coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
