Press "Enter" to skip to content

Tree traversal data structure

Tree traversal is a systematic way of ordering the nodes of a tree. When you are going throw three traversal structure, you will visit each node exactly once.

I use this method in work a few years ago and using it till now. Imagine that you have category table (i’ll be using MSSQL syntax for this post):

CREATE TABLE Categories
(
  ID int IDENTITY(1,1) NOT NULL,
  CategoryName NVARCHAR(100) NOT NULL,
  ParentID INT NULL,
  CONSTRAINT pk_CategoryID PRIMARY KEY (ID)
)
INSERT INTO Categories (CategoryName, ParentID) VALUES ('Computers', NULL); -- ID: 1
INSERT INTO Categories (CategoryName, ParentID) VALUES ('PC', 1); -- ID: 2
INSERT INTO Categories (CategoryName, ParentID) VALUES ('AMD', 2); -- ID: 3
INSERT INTO Categories (CategoryName, ParentID) VALUES ('Pentium', 2); -- ID: 4
INSERT INTO Categories (CategoryName, ParentID) VALUES ('Notebooks', 1); -- ID: 5
INSERT INTO Categories (CategoryName, ParentID) VALUES ('Books', NULL); -- ID: 6
INSERT INTO Categories (CategoryName, ParentID) VALUES ('Sci-fi', 6); -- ID: 7
INSERT INTO Categories (CategoryName, ParentID) VALUES ('Fantasy', 7); -- ID: 8

We have two parent categories ‘Computers’ and ‘Books’. Both of them have subcategories and ‘Computers’ category has subsubcategories as well. Now you will need to get all products from ‘Computers’ category and all subcategories. With this database structure it will be realy hard to get all products. You will need to get all category Ids and join them in IN clause. There is better way how to get them, it’s called tree traversal.

Tree traversal example

Here is image which shows previous data we inserted into category table.

Now we will add numbers to left and right side of each elipse, begining from left parent category, go to subcategories and continuing to right side.

Numbers on left side will be called ‘lft, on right side ‘rtg’. We can now update database structure to contain these informations.

CREATE TABLE Categories
(
  ID INT NOT NULL,
  CategoryName NVARCHAR(100) NOT NULL,
  ParentID INT NULL,
  lft INT NOT NULL,
  rtg INT NOT NULL,
  CONSTRAINT pk_CategoryID PRIMARY KEY (ID)
)
INSERT INTO Categories (CategoryName, ParentID, lft, rtg) VALUES ('Computers', NULL, 1, 10); -- ID: 1
INSERT INTO Categories (CategoryName, ParentID, lft, rtg) VALUES ('PC', 1, 2, 7); -- ID: 2
INSERT INTO Categories (CategoryName, ParentID, lft, rtg) VALUES ('AMD', 2, 3, 4); -- ID: 3
INSERT INTO Categories (CategoryName, ParentID, lft, rtg) VALUES ('Pentium', 2, 5, 6); -- ID: 4
INSERT INTO Categories (CategoryName, ParentID, lft, rtg) VALUES ('Notebooks', 1, 8, 9); -- ID: 5
INSERT INTO Categories (CategoryName, ParentID, lft, rtg) VALUES ('Books', NULL, 11, 16); -- ID: 6
INSERT INTO Categories (CategoryName, ParentID, lft, rtg) VALUES ('Sci-fi', 6, 12, 13); -- ID: 7
INSERT INTO Categories (CategoryName, ParentID, lft, rtg) VALUES ('Fantasy', 7, 14, 15); -- ID: 8

Get child categories

Now we can get all child categories of ‘Computers’ category.

SELECT * FROM Categories WHERE lft >= 1 AND rtg <= 10;
&#91;/sourcecode&#93;
<h4>Get all parent categories</h4>
Another posibility is when we need to create breadcrumbs for actual product page. We know, that the product is in 'Pentium' category. To get all parent categories we will use similar sql to the one above

[sourcecode language='sql']
SELECT * FROM Categories WHERE lft <= 5 AND rtg >= 6 ORDER BY lft ASC;

Have the category any childs?

If you have the category data and need to know if the category have any child categories you will need to make another select which will search for all categories which have ParentID same as your category. With this you can only compare ‘lft’ and ‘rtg’. If ‘lft’ +1 = ‘rtg’ than the category doesn’t have any subcategories.

One Comment

  1. Luca
    Luca August 20, 2012

    interesting method. I’ll see if i can fit this in my tables.

Leave a Reply to Luca Cancel reply

Your email address will not be published. Required fields are marked *