A tree is best thought of in this sort of picture. You have a root node at the very top and it has child nodes and each of those child nodes, they have child nodes themselves, and so on.
Very often when we’re talking about trees we talk about binary trees.
A binary tree means that each node has no more than two child nodes.
That is that each node has a left node and a right node. Of course one or both of those could also be null.
Binary Search Tree
A binary search tree is a binary tree that fulfills a specific ordering property and a special tree data structure. So on any subtree, the left nodes are less than the root node which is less than all of the right notes. This ordering property makes finding a node very fast because we have a pretty good idea of where it would be.
How Searching Works Binary Search Tree?
Let’s choose a node, it’s bigger than the root node, so let’s go to the right. Now the next node, if it’s smaller than that node so it must be on the left unless it should be in right. And so very quickly we can start to zoom in on where that node will be because at each operation we’ve chopped off hopefully about half of the nodes and very quickly we find the node we’re looking for.
Inserting an Element
Inserts work much like finding an element works. We start with some element we want to insert like say, 19, and we say is it bigger or smaller than the route?
Let say, it’s bigger so let’s go to the right. Now compare it to the next node? If it’s smaller so let’s go to the left. We will do this over and over again until we get to an empty spot or a null node and then we say ok that’s where we should insert our new element.
Now the one problem here is that if we get elements in a particular order, we could get really imbalanced. Suppose we have a new binary search tree and we just follow the properties of insertion.
So we insert 1 and then 2 to it’s right and then 3 to it’s right and 4 to it’s right, we’re going to get this data structure that looks less like a tree and more like a long list.
And then inserts and finds will no longer be so fast. There are some algorithms that can ensure that our tree stays balanced, that is roughly the same number of nodes will be on the left side of the subtree and on the right.
These algorithms get pretty complicated so we’re not gonna go into the details here, but it’s worth knowing that they’re built into a lot of programming languages and in a lot of cases and Data Structures Interview Questions you’ll just assume that you have a balanced tree.
Traversing Through a Tree
The last operation to talk about is traversing or walking through a tree. So there are three common ways we walk through a tree we can do an
- Inorder traversal
- Preorder traversal
- Postorder traversal.
A Preorder traversal means that you visit the root first and then you visit it’s left nodes and it’s right nodes.
In Inorder traversal, you visit the left nodes first then the current node and then you go to the right nodes.
In a Post Order Traversal, the root node comes up last so you visit the left nodes and then the right nodes, then the current root node.
Typically in binary search trees, we want to do in order traversals because that actually allows the nodes to be printed in order.
Implement A Binary Search Tree