Tree

 A Tree is a non-linear, hierarchical data structure that consists of a collection of nodes connected by edges. Unlike linear structures (like arrays or linked lists), which store data in a sequential line, trees organize data in a "branching" way that resembles an actual tree -
though in computer science, we usually draw them "upside down" with the root at the top.

 Key Terminology

To understand trees, you need to know the specific names for their parts:

  • Root: The topmost node of the tree. It is the only node with no parent.

  • Edge: The connecting link between two nodes.

  • Parent: A node that has one or more child nodes branching from it.

  • Child: A node that is a descendant of another node.

  • Leaf (External Node): A node that has no children; it is the "end" of a branch.

  • Internal Node: A node with at least one child

  • Subtree: Any node can be viewed as the root of its own smaller tree (a subtree).

  • Degree: The total number of children a specific node has.

Measuring a Tree

  • Level: The distance from the root. The root is at level 0, its children are at level 1, and so on.

  • Depth: The number of edges from the root to a specific node.

  • Height: The number of edges on the longest path from a node to a leaf. The Height of the Tree is the height of the root node.

Comments

Post a Comment

Popular posts from this blog

1. Repeated DNA Sequences

Image
 T he  DNA sequence  is composed of a series of nucleotides abbreviated as  'A' ,  'C' ,  'G' , and  'T' For example,  "ACGAATTCCG"  is a  DNA sequence . When studying  DNA , it is useful to identify repeated sequences within the DNA. Given a string  s  that represents a  DNA sequence , return all the  10 -letter-long  sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in  any order .   Example 1: Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"] Ex ample 2: Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"]
Read more

Top K Elements

Image
  The  top k elements  pattern is an important technique in coding that helps us efficiently find a specific number of elements, known as  k, from a set of data. This is particularly useful when we’re tasked with identifying the largest, smallest, or most/least frequent elements within an unsorted collection. Which data structure can we use to solve such problems? A heap is the best data structure to keep track of the smallest or largest k  elements. With this pattern, we either use a max heap or a min heap to find the smallest or largest k elements, respectively, because they allow us to efficiently maintain a collection of elements ordered in a way that gives us quick access to the smallest (min heap) or largest (max heap) element. Algorithm Max Heap => Smallest k elements Min Heap => Largest k elements Top 3 largest numbers
Read more

1. Valid palindrome

Image
Algorithm: Initialize two pointers, left at the start and right at the end of the string. Iterate until the left pointer is before the right pointer, skipping non-alphanumeric characters for both pointers. Compare characters positioned at the left and right pointers in lowercase; if they differ, return FALSE. Move left forward and right backward to check the next pair of characters. If the traversal completes without mismatches, return TRUE indicating the string is a palindrome. valid palindrome
Read more