Skip to Main Content
Programming Interviews Exposed, 4th Edition
book

Programming Interviews Exposed, 4th Edition

by John Mongan, Noah Suojanen Kindler, Eric Giguere
April 2018
Beginner content levelBeginner
384 pages
11h 3m
English
Wrox
Content preview from Programming Interviews Exposed, 4th Edition

6Trees and Graphs

Trees and graphs are common data structures, so both are fair game in a programming interview. Tree problems are more common, however, because they are simple enough to implement within the time constraints of an interview and enable an interviewer to test your understanding of recursion and runtime analysis. Graph problems are important but often more time-consuming to solve and code, so you won’t see them as frequently.

Unlike the previous chapter’s focus on implementations in C, this and subsequent chapters focus on implementations in more modern object-oriented languages.

TREES

A tree is made up of nodes (data elements) with zero, one, or several references (or pointers) to other nodes. Each node has only one other node referencing it. The result is a data structure that looks like Figure 6-1.

Schematic structure of a data tree made up of nodes (data elements) with zero, one, or several references (or pointers) to other nodes. Each node has only one other node referencing it.

FIGURE 6-1

As in a linked list, a node is represented by a structure or class, and trees can be implemented in any language that includes pointers or references. In object-oriented languages you usually define a class for the common parts of a node and one or more subclasses for the data held by a node. For example, the following are the C# classes you might use for a tree of integers:

public class Node {
    public Node[] children;
}

public class IntNode : Node {
    public int value;
}

In this definition, children is an array that keeps track of all the nodes that ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Beyond Vibe Coding

Beyond Vibe Coding

Addy Osmani
The Programmer's Brain

The Programmer's Brain

Felienne Hermans
Programming Rust, 2nd Edition

Programming Rust, 2nd Edition

Jim Blandy, Jason Orendorff, Leonora F. S. Tindall

Publisher Resources

ISBN: 9781119418474Purchase book