Trees interview questions

Quick facts

Recall the answer first, then tap Show to check.

• @dataclassShowHide

  @dataclass writes __init__, __repr__ and __eq__ from the annotated fields; a tree node needs three fields and no methods.

• Python recursion limitShowHide

  CPython's default recursion limit is 1000 (sys.getrecursionlimit()); a chain-shaped tree deeper than that needs an iterative walk.

• Kotlin nullable childrenShowHide

  var left: Node? = null makes a missing child explicit; node?.left safely returns null when node is null.

• Heap-style indexesShowHide

  Storing a tree in a list with children of index i at 2i + 1 and 2i + 2 is how this course writes test trees, and how binary heaps are stored.

• collections.deque for BFSShowHide

  BFS appends to the right and pops from the left; a deque does both in O(1), a list's pop(0) is O(n).