1.
Problem
1.1.
Left-Leaning Red-Black Tree
2.
Solution
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Insertion in Left-Leaning Red-Black Tree

GAZAL ARORA
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Problem

Design an algorithm to insert nodes in the Left-Leaning Red-Black Tree.

Input: Nodes data to insert in the tree.

Output: The inorder Traversal of the tree.

### Left-Leaning Red-Black Tree

A left-leaning Red-Black Tree(LLRB) is a version of the Red-Black Tree that ensures O(logn) time for all search, delete, and insert operations. We can simulate all Red-Black Tree properties by following the characteristics mentioned below.

Characteristics/ Rules of LLRB.

1. The root node is always Black.
2. The color of every new Node inserted is always Red.
3. Every NULL child of a node is Black.
4. If a node has a right Red child and a left Black child (or NULL child because all NULLS are Black), left rotate the Node and swap the colors of the current Node and its left child to keep rule 2 consistent, i.e., the new Node must be Red.

Example,

1. If there is a node with a left Red child and a left RED grandchild, right-rotate the node and swap the colors of the current node and its right child to keep rule 2 consistent, i.e., the new node must be Red.

For example,

1. If a node has a left Red child and a Right Red child, invert the colors of the current node, left child, and the right child.

For example,

Letâ€™s understand with an example,

Alert Ninjas:  Donâ€™t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and space-efficient code and compete in code competitions worldwide.

Recommended: Try to solve it yourself before moving on to the solution.

## Solution

Idea: The idea is to do insertions just like insertions in the Binary Search Tree. At every step, retrace back to the root and enforce the rules as mentioned above for LLRB.

Point to remember: The root may turn red while performing the above rotations and color swaps. We must ensure that the color of the root is always Black.

C++

Input: Insert in the order 2, 4, 6, 5.

Output:

The output tree is

Time Complexity:  O(log n), same as a BST.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## FAQs

1. What is a Red-Black Tree?
A red-black tree is a self-balancing binary search tree with one extra bit at each node, which is a color (red or black). These colors are used to keep the tree balanced during insertions and deletions.

2. What is a Binary Search Tree?
A binary search tree (BST) is a binary tree in which each node has a Comparable key (and an associated value) greater than the keys in all nodes in its left subtree and smaller than the keys in all nodes in its right subtree.

3. Why do we use Red-Black Trees?
In the worst case, a BST may have a height of O(n) that takes O(n) time for search, insert, or delete operations, but a red-black tree is a height-balanced  BST with a worst-case height of O(logn).

## Key Takeaways

In this article, we learned about the characteristics of the Left-Leaning Red-Black Tree and designed an algorithm to do insertions in it.

With the help of an example, we learned about left rotations, right rotations, and color swapping to keep the tree height-balanced.

You can learn about trees from here.
Check out this problem - Largest BST In Binary Tree

Apart from that, you can use Coding Ninjas Studio to practice a wide range of DSA questions asked in lots of interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.

Live masterclass