Binary Tree vs Binary Search Tree: Key Differences Explained with Examples

In the world of data structures, trees are a fundamental concept used to organize and manage data efficiently. Two commonly used types of trees are Binary Tree and Binary Search Tree (BST). While they sound similar and are both hierarchical structures, they serve different purposes and follow different rules. This blog will explain the key differences between a Binary Tree and a Binary Search Tree, along with practical examples to help you understand when and why to use each.#BinaryTree #BinarySearchTree #DataStructures #DSA #Algorithms

What is a Binary Tree?

A Binary Tree is a hierarchical data structure in which each node has at most two children—commonly referred to as the left child and the right child. There are no strict rules regarding how data is organized within the tree.

Key Characteristics of a Binary Tree:

• Each node has at most two children.
• There’s no condition on how values are arranged.
• It can be used to represent expressions, hierarchies, or even as a base for more specialized trees.

Example of a Binary Tree:

1 / \ 2 3 / \ 4 5

In this example, each node follows the binary tree rule (two children max), but there’s no specific order to the values.

What is a Binary Search Tree (BST)?

A Binary Search Tree (BST) is a specialized version of a binary tree where nodes are organized based on comparison rules. In a BST:

• The left subtree of a node contains only nodes with values less than the node’s value.
• The right subtree of a node contains only nodes with values greater than the node’s value.
• This structure enables efficient searching, insertion, and deletion operations.

Example of a Binary Search Tree:

8 / \ 3 10 / \ \ 1 6 14

Here:

• Nodes in the left subtree of 8 (3, 1, 6) are all less than 8.
• Nodes in the right subtree (10, 14) are greater than 8.
• This arrangement allows for fast binary search operations.

Key Differences Between Binary Tree and Binary Search Tree

Feature Binary Tree Binary Search Tree Node Arrangement No specific order Left < Root < Right Purpose General data structure Fast lookup, insert, delete Search Time O(n) in worst case O(log n) in average case Duplicates Allowed Usually not allowed Use Case Expression trees, hierarchical structures Databases, search operations Traversal Any traversal works In-order gives sorted output Implementation Complexity Simple Requires careful insertion

Operations and Efficiency

Binary Tree:

• Insertion: No rule for positioning, so it can be placed anywhere logically.
• Search: May need to search all nodes—O(n) time complexity.
• Use Case: Great for representing abstract syntax trees, parsing expressions.

Binary Search Tree:

• Insertion: Based on comparison—place smaller values to the left, greater to the right.
• Search: Efficient if tree is balanced—O(log n) average time complexity.
• Use Case: Ideal for dictionaries, dynamic sets, database indexing.

Practical Use Cases

When to Use a Binary Tree:

• You’re building parse trees for compilers.
• You want to represent structured data like a family tree, organization chart, or decision tree.
• Order doesn’t matter, but relationships do.

When to Use a Binary Search Tree:

• You need fast data access (search, insert, delete).
• You are implementing data-intensive applications like:
• Databases
• Symbol tables
• File systems
• Search engines
• You want a structure that maintains a sorted order.

Example in Code (Python)

Binary Tree Implementation:

class Node: def __init__(self, key): self.key = key self.left = None self.right = None root = Node(1) root.left = Node(2) root.right = Node(3)

Binary Search Tree Insertion:

class BSTNode: def __init__(self, key): self.key = key self.left = None self.right = None def insert(node, key): if node is None: return BSTNode(key) if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node root = BSTNode(8) insert(root, 3) insert(root, 10) insert(root, 1)

In-Order Traversal in BST

In a BST, in-order traversal (Left → Root → Right) will always give a sorted list of values:def inorder(node): if node: inorder(node.left) print(node.key, end=“ ”) inorder(node.right) # Output for BST: 1 3 8 10

Conclusion

Understanding the differences between a Binary Tree and a Binary Search Tree is crucial for selecting the right data structure based on your project requirements. A Binary Tree is flexible and general-purpose, while a Binary Search Tree is structured and optimized for search operations. Each has its own advantages and limitations, and choosing the right one depends on your specific use case.

By mastering both, you equip yourself with the tools needed to solve a wide range of algorithmic problems efficiently.

Test Your Knowledge: Quiz Challenge!!! 📝🧠

Which hash function is used in the division method?🤔

For more interesting quizzes, check the link below! 📚
https://bit.ly/42qN0sr

For the explanation of the right answer, you can check Q.No. 20 of the above link. 📖

Test Your Knowledge: Quiz Challenge!!! 📝🧠

We are given a set of n distinct elements and an unlabelled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?🤔

For more interesting quizzes, check the link below! 📚
https://bit.ly/42qN0sr

For the explanation of the right answer, you can check Q.No. 19 of the above link. 📖

What is a Strict Binary Tree?
.
.
.
.
for more information
http://bit.ly/40G9fsh
check the above link

Leetcode Çözümleri - Binary Tree Inorder Traversal

LeetCode Çözümleri - 226. Invert Binary Tree

binary-tree cord-stops bag #binarytree #0000001 #tshirt & #shoestring
https://www.instagram.com/p/BqKZKt1HU3B/?utm_source=ig_tumblr_share&igshid=7ndrly6t34u1

Binary trees in the video. Finally, I uploaded a video presenting the animation of procedurally generated trees.

#binary #trees #binarytree #opengl #fractal #tree #nature #youtube #yt #cplusplus #winapi #project #development #recursion #animation #cgi #video #motion #wind #tech #technology #visualstudio #codeblocks #programming #coding #realtime #indiedev #gamedev #generativeart #generative
https://www.instagram.com/p/Bm1aPGcFBkf/?utm_source=ig_tumblr_share&igshid=1bpoqz2lb5vt8

Q. Given a binary tree, find the bottommost leftmost node of the tree. [link]

A. Whenever a question asks you to do some level wise operation on a tree, breadth first search should be the first thing to remember. If you have not read about it, BFS traversal is a level order traversal (read about it before moving any further). 

One more thing to remember is that BFS is always implemented using a Queue data structure (why?). When we use a queue to implement BFS traversal, by default we always push the left node into the queue and then we push the right node into the queue. 

So, basically the last element we pop from the queue is the rightmost bottommost node of the tree (how?). How can we reverse this logic to get the bottommost leftmost node of the tree at the end?  

Yes, we push the right node in the queue and then we push the left node in the queue. This way, we get the bottommost leftmost node of the tree when we pop the last element of the queue. 

Hey! I’ve fallen behind a little bit due to a huge load of assignments and midterms over the past 3 weeks, but I’ll still make sure to keep to date!

Binary Trees are an ADT we derived from Trees, which we learned about last week. Binary Trees are simply Trees, however they only have two children, which are specified in the class initializer as left and right. This allows for us to branch into other types of the Tree ADT, a couple being: the Arithmetic Expression Tree, and the Binary Search Tree. 

The Arithmetic Expression Tree simply allows us to calculate an arithmetic expression through the use of a binary tree. Each parent node is an arithmetic expression while each of the left and right nodes will equate to a number. In it’s simplest form, an Arithmetic Expression Tree would look something like:

   + 

1     2. If we use a function we made in class to evaluate this tree, we would get 3.

Binary Search Trees are probably the most important type of the Tree ADT, because it means that the tree is balanced. This means that the data on the left is less than the root, which is less than the data on the right (remembering the definition of a Binary Tree being that there is two nodes). This can easily half the time it takes to search for a value in a tree, and makes navigating a  Binary Tree much quicker and easier. This idea of being more efficient will be looked at in the coming weeks.

The horizontal distance is a metric for the binary trees that is computed in relation to the parent and the position of the node (left, right). 

Here is the formula:

0 for the root
the left child has the distance of its parent -1
the right child has the distance of its parent +1

Between the two children of the same node, there is a horizontal distance of two. As the tree is expanded, the nodes may form vertical lines and in this case they will have the same horizontal distance. 

Using horizontal distance, it’s possible to have a nice visual representation of the tree. We are able to measure the necessary width of the window that contains the tree as the absolute difference of max distance and min distance of all nodes.

Apparently, the implementation of the binary tree pictured below ignores this ingenuous trick.

I associated integer values to the nodes that transform it into a BST, but this is not important for the example. What’s relevant is the value between the parenthesis which represents the horizontal distance. The root has 0, as we go down in the left subtree, the node with value 3 has the distance -1 (0-1), node with value 2 the distance -2 (-1-1) and so on.

If you put your imagination to work, you will be able to see vertical lines connecting nodes with the same horizontal distance. There’s a special case I wanted to include in here, the nodes 5 and 7 have both horizontal distance 0 so they would overlap in a graphic representation.

The code for computing horizontal distances and the complete vertical view is below. The result is a sorted dictionary that stores the horizontal distance as key that points to a list of nodes with this distance .

/// Vertical view works with the concept of horizontal distance
/// The horizontal distance is computed like this:
/// 0 for the root
/// the left child has the distance of its parent -1
/// the right child has the distance of its parent +1
/// nodes having the same horizontal distance form a line
/// the vertical view means displaying the collection of those vertical lines
/// 
public static SortedDictionary<int, List<T>> VerticalView(NodeTree root)
{
    var distances = new SortedDictionary<int, List<T>>();
    horizontalDistance(root, 0, distances);
    return distances;
}

private static void horizontalDistance(NodeTree<T> node, int distance, SortedDictionary<int, List<T>> distances)
{
    if (node == null)
    {
        return;
    }

    updateHorizontalDistance(x => x - 1, distance, node.Left, distances);
    updateHorizontalDistance(x => x + 1, distance, node.Right, distances);
}

private static void updateHorizontalDistance(Func<int, int> horizontalDistanceComputer, int distance,
    NodeTree<T> node, SortedDictionary<int, List<T>> distances)
{
    if (node != null)
    {
        int leftDistance = horizontalDistanceComputer(distance);
        List<T> values;
        if (!distances.TryGetValue(leftDistance, out values))
        {
            values = new List();
            distances[leftDistance] = values;
        }
        values.Add(node.Data);

        horizontalDistance(node, leftDistance, distances);
    }
}
        
    

Vachellia Abyssinica - also known as Flat Top Acacia trees.

Everybody’s favorite way of traversing a tree since it’s so visual. Plus, it gets you the nodes sorted in a binary search tree.

If I see a tree picture, I can write down the inorder of nodes just by reading all of their projections from left to right. Very useful when testing BT algorithms.

Now for coding. The inorder recursion is obvious, but what if recursion should be avoided? Going back and forth in the tree suggests using the stack, so my solution will do just that. I keep pushing nodes to the stack while they have a left child and when I backtrack, I add the node to the result and continue on its right child.

With recursion:

        
public static List<T> Inorder(NodeTree<T> node)
{
    if (node == null || Equals(node.Data, default(T)))
    {
        return null;
    }

    List<T> left = Inorder(node.Left) ?? new List();

    left.Add(node.Data);

    List<T> right = Inorder(node.Right);

    return right != null ? left.Concat(right).ToList() : left;
}
        
    

and with a stack:

    
public static List<T> InorderWithStack(NodeTree<T> node)
{
    var result = new List<T>();
    if (node == null)
    {
        return result;
    }

    var stack = new Stack<NodeTree<T>>();
    stack.Push(node);

    // when backtracking, avoid reading the left child since it was processed
    bool finishedWithLeftChild = false;
    while (stack.Count > 0)
    {
        NodeTree<T> cur = stack.Peek();
        if (!finishedWithLeftChild && cur.Left != null)
        {
            stack.Push(cur.Left);
        }
        else
        {
            result.Add(cur.Data);
            stack.Pop();
            finishedWithLeftChild = true;
            if (cur.Right != null)
            {
                stack.Push(cur.Right);
                finishedWithLeftChild = false;
            }
        }
    }
    return result;
}
    

Try imagining a binary tree with a decent set of nodes. How would you do to find all the nodes that are situated at a certain distance from the root? How would you do to find all the nodes that are at a certaing distance from the leaves?

Let’s look at a tree picture that I took from geeksforgeeks.org:

If the root is the node having the value 60, there are two nodes at one step distance, 41 and 74. How many of them are at distance 3 then? In a manner similar to breadth first search, we can look at all the nodes on level 3 to find the answer.

In my code, I start searching from the root node and use recursion to go down on a node’s left and right children. Whenever a node is at the required distance, I add it to the result.

public static List<NodeTree<T>> NodesAtDistanceK(NodeTree<T> node, int distance, int curDistance = 0)
{
    var result = new List<NodeTree<T>>();
    
    // not a valid node
    if (node == null)
    {
        return result;
    }
    
    if (distance == curDistance)
    {
        // found a node that qualifies
        return Enumerable.Repeat(node, 1).ToList();
    }

    // check for the nodes in the left subtree
    List<NodeTree<T>> foundLeft = NodesAtDistanceK(node.Left, distance, curDistance + 1);
    if (foundLeft.Any())
    {
        result = foundLeft;
    }
    
    //check the nodes on the right subtree
    List<NodeTree<T>> foundRight = NodesAtDistanceK(node.Right, distance, curDistance + 1);
    return foundRight.Any() ? (result.Any() ? result.Concat(foundRight).ToList() : foundRight) : result;
}
           

For a distance of 3, the answer is: 25, 46, 55, 63, 70.

Now onto the second problem, searching all nodes that find themselves at a given distance from a leaf. Descending from our node to the leaves may be done using various paths, so the node may be closer to a leaf than to the others. The problem can be restated as: find all the nodes that have at least a leaf at given steps away.

In the code, at each step, I return an array of distances from the current node to all reachable leaves. The collection of all nodes that validate the distance is passed as a parameter and it can be augmented as we traverse the tree.

public static List<int> DistanceFromLeaves(NodeTree<T> currentNode, int distanceToHit, List<NodeTree<T>> result)
{
    if (currentNode == null)
    {
        return Enumerable.Empty<int>().ToList();
    }

    // check the left side
    List<int> distanceLeft = DistanceFromLeaves(currentNode.Left, distanceToHit, result);
    
    // check the right side
    List<int> distanceRight = DistanceFromLeaves(currentNode.Right, distanceToHit, result);

    if (!distanceLeft.Any() && !distanceRight.Any())
    {
        // a leaf
        return Enumerable.Repeat(1, 1).ToList();
    }

    // check all leaf distances, avoid duplicated distances
    List<int> distances = distanceLeft.Concat(distanceRight).Distinct().ToList();
    if (distances.Any(x => x == distanceToHit))
    {
        result.Add(currentNode);
    }

    // increment distances to take into account current step
    for (int i = 0; i < distances.Count; i++)
    {
        distances[i]++;
    }

    return distances;
}
        

If we use the same binary tree depicted in the photo, the list of nodes at distance 3 from a leaf is: 41, 74, 60

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

   1         3     3      2      1

    \       /     /      / \      \

     3     2     1      1   3      2

    /     /       \                 \

   2     1         2                 3

The unique binary search tree can be generated recursively by 

• Start with a root number K where K in [1, N]
• Generate unique binary search tree from 1 to K - 1 as left child.
• Generate unique binary search tree from K + 1 to N as right child.
• Construct the tree, it is a set of trees in the end.

You can read my code here.

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

   1         3     3      2      1

    \       /     /      / \      \

     3     2     1      1   3      2

    /     /       \                 \

   2     1         2                 3

For a BST N the unique number of BST actually equals to the unique number of BST on left children multiply the number of unique BST on right children.

So we can write the following formula M[n] which represents the number of unique BST for N

M[n] = Sum(M[i] * M[n - i - 1], i belongs to [0, n - 1])

M[0] = 1

You can read my code here.

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Pass the allowed range and do a recursion to validate the tree. 

You can read my code here.

So I learnt about Trees in my Computer Science logic class a few weeks ago and my teacher said something along the lines of “That’s why Computer Scientists are different from everyone else; our tree roots are at the top.”

Now anytime I see a tree, I try to imagine it as a Computer Science tree, with the roots at the top.

One of these days, I want to examine an actual tree and see if it can be a binary tree.