Everything About Trees - Depth First Search / Introduction


The tree depicted in diagrams are undirected. In graph theory, tree is indeed an undirected graph. But in the context of programming as a data structure, it is a rooted and directed acyclic graph. It will be useful to specify this context difference as well as update the tree diagrams.

You dont have F in the output of the pre-order traversal example

Definition of internal node is incorrect.

Isnt the description of the depth and the first diagram incorrect?

Depth at the root is 1, not 0

Incorrect. The depth at the root node is always 0. How do you propose we traverse greater than 0 edges to get from the root node to the root node?

The gifs for pre-order, in-order and post-order traversals are all the same, this is wrong.

the sequence of the text on the nodes are different.

I had a question about why the implementation of a tree node did not have a pointer to it’s parent node i.e. why doesn’t a node have the property node.parent?

I found this link helpful and I thought I would share: https://stackoverflow.com/questions/10426636/why-a-lot-of-binary-tree-data-structures-in-c-do-not-have-a-parent-node-pointer

The animation of the pre-order, in-order and post-order traversals keeps flashing. It’s very distracting. Can you switch to a play-stop way to display or slow down the speed?

Go code lacks the imports, so doesn’t compile out of the box.

The is missing import (import java.util.Scanner;) on In-order Traversal example to run successfully!

There is*

The images should have the same structure of graph… not the same output across each traversal with different graph structure – its confusing

when comparing inorder,preorder,post-order traversal

The height of the A and B nodes are wrong in the 2nd example, tree summary

I think the reason about why last diagram in the first section is not a tree is incorrect. Since we can’t go from node D to node B, there’s not cycle in the graph. It is “node D has two parent nodes” that makes it not a tree.

The height diagram is incorrect. The longest path from the root to a leaf is 3, not 4.

One representation help me with to understan how encode bin tree:

 stack frames:
   |     |      | x
   |     | 3    | x
   |  4  |      | x
5  |     |  8   | x
   |  6  | x    |
   |     |x

From the input the trees are built with pre-order traversal. I am really curious if we could build the trees using post-order or in-order traversal. I’ve been trying to write the code and searched the internet but to no avail! The reason I’m doing this is to get better understanding about what happens with each traversal. Any help is much appreciated!