AlgoDaily - An Executable Data Structures Cheat Sheet for Interviews

Tree

Quick summary: a data structure that stores a hierarchy of values.
Important facts:
- Organizes values hierarchically.
- A tree item is called a node, and every node is connected to 0 or more child nodes using links.
- A tree is a kind of graph where between any two nodes, there is only one possible path.
- The top node in a tree that has no parent nodes is called the root.
- Nodes that have no children are called leaves.
- The number of links from the root to a node is called that node's depth.
- The height of a tree is the number of links from its root to the furthest leaf.
- In a binary tree, nodes cannot have more than two children.
  - Any node can have one left and one right child node.
  - Used to make binary search trees.
  - In an unbalanced binary tree, there is a significant difference in height between subtrees.
  - An completely one-sided tree is called a degenerate tree and becomes equivalent to a linked list.
- Trees (and graphs in general) can be traversed in several ways:
  - Breadth first search (BFS): nodes one link away from the root are visited first, then nodes two links away, etc. BFS finds the shortest path between the starting node and any other reachable node.
  - Depth first search (DFS): nodes are visited as deep as possible down the leftmost path, then by the next path to the right, etc. This method is less memory intensive than BFS. It comes in several flavors, including:
    - Pre order traversal (similar to DFS): after the current node, the left subtree is visited, then the right subtree.
    - In order traversal: the left subtree is visited first, then the current node, then the right subtree.
    - Post order traversal. the left subtree is visited first, then the right subtree, and finally the current node.
Pros:
- For most operations, the average time complexity is O(log(n)), which enables solid scalability. Worst time complexity varies between O(log(n)) and O(n).
Cons:
- Performance degrades as trees lose balance, and re-balancing requires effort.
- No constant time operations: trees are moderately fast at everything they do.
Notable uses:
- File systems.
- Database indexing.
- Syntax trees.
- Comment threads.
Time complexity: varies for different kinds of trees.
See also:
- Interview Problems: Trees

xxxxxxxxxx
console.log(children[1].getParentNode());
 
function TreeNode(value) {
  this.value = value;
  this.children = [];
  this.parent = null;
​
  this.setParentNode = function (node) {
    this.parent = node;
  };
​
  this.getParentNode = function () {
    return this.parent;
  };
​
  this.addNode = function (node) {
    node.setParentNode(this);
    this.children[this.children.length] = node;
  };
​
  this.getChildren = function () {
    return this.children;
  };
​
  this.removeChildren = function () {
    this.children = [];
  };
}
​

OUTPUT

Results will appear here.