Interview Cheat Sheets | Tree Cheat Sheet

December 22nd, 2023

Introduction

This article will serve to further summarize the excellent overview of trees from the tech interview handbook.

Overview:

  • A tree is an abstract data type representing a hierarchical structure.
  • Trees are undirected, connected, and acyclic graphs used to represent hierarchical relationships in various data structures like file systems, JSON, and HTML documents.
    • There are no cycles or loops. Each node can be like the root node of its own subtree, making recursion a useful technique for tree traversal.
  • For interviews, binary trees and binary search trees (BST) are commonly discussed.

Common Terms:

  • Neighbor - Parent or child of a node
  • Ancestor - A node reachable by traversing its parent chain
  • Descendant - A node in the node’s subtree
  • Degree - Number of children of a node
  • Degree of a tree - Maximum degree of nodes in the tree
  • Distance - Number of edges along the shortest path between two nodes
  • Level/Depth - Number of edges along the unique path between a node and the root node
  • Width - Number of nodes in a level

Binary Tree:

  • Binary trees consist of nodes with a maximum of two children.
  • Complete binary tree - A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
  • Balanced binary tree - A binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.
  • Traversals include in-order (Left -> Root -> Right), pre-order (Root -> Left -> Right), and post-order (Left -> Right -> Root).

Binary Search Tree (BST):

  • In-order traversal of a BST provides elements in order.
  • Properties and validation of a BST are crucial.

Time Complexity:

OperationBig-O
AccessO(log(n))
SearchO(log(n))
InsertO(log(n))
RemoveO(log(n))

The space complexity of traversing balanced trees is O(h) where h is the height of the tree, while traversing very skewed trees (which is essentially a linked list) will be O(n).

Interview Considerations:

  • Emphasis on recursive traversals (pre-order, in-order, post-order) and iterative approaches.
  • Handling corner cases: empty tree, single node, two nodes, and skewed tree.

Techniques:

  • Recursive approaches are common for tree traversal; base case checks are crucial, usually when a node is null.
  • Level-wise traversal is essential for breadth-first search.

Essential Questions:

  • Binary Tree:

    • Maximum Depth of Binary Tree
    • Invert/Flip Binary Tree: My solution
  • Binary Search Tree:

    • Lowest Common Ancestor of a Binary Search Tree - My solution
  • Binary tree
    • Same Tree
    • Binary Tree Maximum Path Sum
    • Binary Tree Level Order Traversal
    • Binary Tree Right Side View - My solution
    • Subtree of Another Tree
    • Construct Binary Tree from Preorder and Inorder Traversal
    • Serialize and Deserialize Binary Tree
  • Binary search tree
    • Validate Binary Search Tree - My solution
    • Kth Smallest Element in a BST