The Self-Taught Computer Scientist

Figure 14.7: Binary search trees operation run times

---

Chapter 14 Binary Trees
151
be difficult or impossible to represent in a linear data structure like an array. For example, imagine 
you wanted to represent the directories on your computer programmatically. You may have a Documents 
folder with 10 folders in it, and each of those folders has 20 folders in it, and each of those folders has 
4 folders in it, etc. Representing the relationship between folders on your computer and what directory 
a user is in would be confusing and challenging to do using an array, but with a tree, it is easy 
(Figure 14.8).
HTML and XML documents are another example of hierarchical data computer scientists represent 
with trees. HTML is a markup language you can use to create web pages. XML is a markup language 
for documents. You can nest HTML and XML tags, so programmers often store them as trees where 
each node represents a single element in the HTML or XML. When you are programming the front 
end of a website, the programming language JavaScript gives you access to the document object model 
(DOM). The document object model is a language- independent interface that models an XML or 
HTML document as a tree (Figure 14.9).
Continents
Asia
India
Italy
London
Essex
Germany
USA
England
Munich 
Berlin
Europe
North America
Figure 14.8: An example of folders in a tree

---

Data Structures
152
You can use a tree to parse things like arithmetic expressions. For example, you can evaluate an 
expression like 2 + 3 * 4 by creating a tree like the one in Figure 14.10. You then evaluate the bottom 
of the tree (3 * 4) and then move up a level to calculate the final solution (2 + 7). A tree like the one 
in Figure 14.10 is called a parse tree. A parse tree is an ordered tree that stores data according to some 
type of syntax, like the rules for evaluating an expression.
Document
Root Element:

Element:

Element:

Element: