Stuti Verma

Quickstart Trees on LeetCode

This is a beginner lab and primer to start solving questions on trees in Data Structures and Algorithms. What is a tree? A tree is a data structure that looks like this:                       4️⃣                                     /          \                        3️⃣              5️⃣            /      \          /     \         1️⃣        2️⃣     6️⃣     7️⃣  Why does it look like this? In the above representation, it is what we call a tree and each point holding a value is called a node. A node is classified depending on it's placement in the structure.  Node with value 4 --> called root node coz it has no parent above it Node with value 3 --> is left child of root node, sibling of node with value 5 and parent node of nodes with value 1 and 2. Node with value 1 --> is left child of node with value 3, sibling of node with value 2 and also called leaf node as it doesn't have any children. Node with value 2 --> is right child of node with value 3, sibling of node with value 1 and also called leaf node as it doesn't have any children. Node with value 5 --> is right child of root node, sibling of node with value 3 and parent node of nodes with value 6 and 7. Node with value 6 --> is left child of node with value 5, sibling of node with value 7 and also called leaf node as it doesn't have any children. Node with value 7 --> is right child of node with value 5, sibling of node with value 7 and also called leaf node as it doesn't have any children. Let's summarize! We have four leaf nodes -> 1, 2, 6, 7 three parent nodes -> 4, 3, 5 one root node -> 4 one tree -> type binary as there are maximum two children nodes of parent nodes Why do we need to traverse? To find out tree node value To make calculations on the basis of tree node value How to define node using code? (naiice, it rhymes :p) class Node: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right What are the algorithms to traverse trees? There are many but we will look at three ways to walk through a tree. Pre-order In-order Post-order Level-order

Mathematics of height and nodes in Trees and Heaps

The height of a node in tree: - is the length of the path from that node to the deepest node in the tree. - is zero for a tree with only one node (i.e. root node).   The height of tree: - is the maximum height among all the nodes in the tree. - is not the same as the height of a node in a tree unless, it is a root node. - is equal to the depth of the tree (in value but not in concept and it can be different for height of node). - is represented as h, here.   Now, let's see the height:                       4️⃣                       - > Height = 2 for all nodes at this level                  /          \                        3️⃣              5️⃣              - > Height = 1 for all nodes at this level            /      \          /     \         1️⃣        2️⃣     6️⃣       7️⃣        - > Height = 0 for all nodes at this level

Talks at Events (7)