This is perhaps the most important data structure, algorithm question in technical interviews. Big tech loves these tree based interview questions. These data structure test your ability to think logically, account for edge cases, use recursion, and use efficient algorithms.
Trees are popular among top tech companies. They always appear in competitive interviews at FAAANG, Facebook Apple Airbnb Amazon Netflix and Google, companies.
FAAANG companies, big techs are Facebook (now META), Apple, Amazon, Airbnb, Netflix, Google. FAAANG companies (big tech, Facebook Apple Airbnb google amazon Netflix LOVE asking tree algorithms interview questions. This is a useful concept to test candidates’ data structure, algorithm, iterative & recursive programming skills, even search algorithms. To solve tree data structure problems, you will want to think logically, think about edge cases if any (example duplicate node value, node with end of word token), use recursion on subtrees, use efficient algorithms to traverse the tree. Also you will want to think about how to change the tree when inserting (adding) or deleting from the tree.
Why are trees, as a data structure, useful? Use case of tree as a data structure (public) Each element in a tree is called a node. Node can contain a value or a list of values. Each node can have reference to the next node, such as node.left (left child) or node.right (right child). If there is no child, we can set the child to None type node.child = None for example. The line that connects two nodes is called an edge. Nodes can also be called vertices (V) and edges can be denoted using big E. Trees are hierarchical, unlike graphs which can be cyclical. Trees are great for modeling hierarchical data. Trees are special cases of graphs. Graph problems are easier to resolve when there are no cycles. For example, DFS can be used in graph traversal
Nodes at end of a tree without children are called leaves. Leaves are useful as ending condition in tree traversal recursions in DFS for example.
There are two major ways to traverse trees: depth first search (DFS), breadth-first search (BFS). Tree concept : What's the difference between balanced tree, complete tree, full tree etc. Pro tips Here's more pro insight on balanced tree
To apply for FAAANG big tech companies with awesome perks, mastering tree traversal and insert updates is perhaps the most important. Read more here ... Uniqtech insights, pro tips for tree traversal When typing tree interview questions in a notepad or during white board sessions you can use the forward backward slashes /\ to represent edges. Read more here... [public]
Tree traversal basics and preorder traversal ... Read more here ... Uniqtech insights, pro tips for tree traversal
In-order Tree traversal pseudo code and detailed explanation [pro, high quality, pro tip]
Tree traversal with recursion [new, improved, pro, illustrated]
It should be distinguished from Binary Search Tree (BST). Used to be a part of high school AP computer science. Each binary tree node will have the max of two children, usually called left child and right child. It's okay for one of them to be empty e.g. node.left == None returns True. Because binary tree propagates with max of two children at a time, its oversize is easy to estimate. With every level, the tree grows by a factor of 2. For example, the first level is the root 2 to the 0th power is 1. Then 2**1 is 2, then 2**2 is 4, so the third level contains max of 4 nodes. Base 2 math is easy and natural in computer science, so binary tree is quite useful.
Common technical interview Data structure tree, binary search tree (BST) Binary Search Tree (BST) common data structure Pro tip: Key insight, pro tip of Binary Search Tree (BST) Here we explain ... Why is binary search efficient Example interview question here with solution ... Interview Question: find min in Binary Search Tree (BST) (with solution)
Graph Basics: the basic components of a graph include nodes and edges (E). Nodes are also called vertices (V).
Graph traversal: We can categorize graph traversal by approaches: There’s depth first search (DFS) and Breadth First Search (BFS). Moving through the graph is also called traversal. We can also categorize by order: preorder, inorder and postorder.
Graph representation
Graph Big O Notation: often graph traversal and graph algorithms Big O notation is a function of both the Edges (E) and Vertices (V). For example, O(V,E). Sometimes it is more specific: O(V + E)
Graph use cases: Graphs are great for modeling networks such as cities, flights, social network.