Trees - A Fundamental Data Structure
A good way to check if a tree is a tree is "if all the tree's edges are drawn with straight lines, none of the lines must overlap". If the lines aren't straight or if they do overlap, then it's not really a "tree" because there wouldn't be a proper hierarchy.
Binary Trees are special trees. All nodes in the tree have at most two child nodes (usually labeled as "left" or "right").
Binary Search Trees
Perfect Binary Search Trees
Binary Tree C++ Code
Let's look at how a binary tree is represented in C++. A node is just a structure that has three (or more) variables inside of it: a pointer to a left child, a pointer to a right child, and the actual data that we care about storing.
(Notice the difference in syntax between the . and -> operators. If we have a variable that actually represents a a node (like node root;) then we use the . operator, but when talking about a pointer to a node, we use the
Okay, so we can create a tree, but how do we actually use it? Tree traversal is typically done using recursion, and there are three types of traversals that matter.
Remembering these three traversal types will help when writing a recursive function, since it dictates the placement in the function's code.
Tree Traversal C++ Code
The following code demonstrates tree traversal techniques. Simply create the tree, and pass the root of the tree to functions to print the traversed nodes.
With this fundamental tree knowledge, we can look to more advanced questions (since trees are popular in interviews).
In future tutorials, we'll look at some tree interview questions that have to do with special traversal or placement of items in the tree. In another tutorial, we'll look at advanced tree data structures and concepts, such as balancing a Binary Tree so that it can become a BST, or looking at how red-black trees work.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Hi, I'm srcmake. I play video games and develop software.
Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.