Below are some notes I took from the excellent Data Structure course at coursera.

A binary tree is a data structure that is extremely handy for representing certain constructs in computer science.

For example, you can use a binary tree to represent a sentence.

sentence.PNG

A syntax tree for an expression.

syntax-tree.PNG

Or abstract tree for code.

code-tree.PNG

And when you order the nodes on your tree, you can have the number of elements when doing search. Which is why binary search trees are so popular for searching.

binary-search-tree.PNG

What is a binary tree?

A binary tree consists of a node, with with one or two other nodes hanging off it. It’s called binary, because each node can only have at most two other nodes hanging off it. And usually when you sort your tree, you put the lower values on the left branch of the node, the the higher value ones on the right.

That’s what makes search with binary trees so quick. You effectively start in the middle, and at most only really need to search half the tree.

defn-binary-tree.PNG

Common operations

The amount of time it takes to search a tree, is proportional to it’s height. That’s why many binary trees have a method that can tell you how high they are.

height.PNG

Another common operation is size (or how many nodes).

size.PNG

One thing you’ll notice when you look at binary tree algorithms is their heavy use of recursion. Recursion is one of those things that can make your head hurt a bit at first, because from within a method, you continuously call yourself again and again. A dream within a dream.

But it is also what makes binary trees so elegant. With very little code you get a lot of amazing functionality. When is why they are so beautiful to study and understand.

Walking trees

There are different ways you can walk a tree which fall into two general categories:

  • Depth first
    • InOrderTraversal
    • PreOrderTraversal
    • PostOrderTraversal
  • Breadth first
    • LevelTraversal

But I am not really sure yet when one would make more sense over the other. I suspect InOrderTraversal would be common.

So anyways, there are some notes on binary trees.

Advertisements