Stuti Verma - SSE@Ottimate, Director@WomenWhoCodeDelhi

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 <ul> <li>four leaf nodes -> 1, 2, 6, 7</li> <li>three parent nodes -> 4, 3, 5</li> <li>one root node -> 4</li> <li>one tree -> type binary as there are maximum two children nodes of parent nodes</li> </ul> Why do we need to traverse? <ul> <li>To find out tree node value</li> <li>To make calculations on the basis of tree node value</li> </ul> How to define node using code? (naiice, it rhymes :p) <pre class="language-python"><code>class Node: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right</code></pre> What are the algorithms to traverse trees? There are many but we will look at three ways to walk through a tree. <ul style="list-style-type: square;"> <li>Pre-order</li> <li>In-order</li> <li>Post-order</li> <li>Level-order</li> </ul>

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)