Data Structure Implementation to Query Binary Tree for Upline / Downline Node without using Recursion

Introduction

We are now and then faced with the problem with storing data corresponding to Binary Tree and querying it. We generally rely on Recursion (hence costly) to query tree structure. Here is a simple data structure change in order query tree structure using simple SQL statement - no Recursion required.

Background

There are situations when we want to store Nodes of binary tree in database with reference to its parent together with position (in this case, Left Node or Right Node of Parent). The problem arises when we want to query database to get upline node or downline Node w.r.t. a certain node, or we want to get the count of nodes present at each level in the b-tree.

You can think of an implementation of this code sample in creating data structure to keep members with their hierarchy for Multi-Level Marketing company.

Using the Code

• Download SQL Scripts
• akyBinaryTreeSQL - 4.82 KB,
• akyBinaryTreeQuery - 4.11 KB

The proposed solution has 2 data tables and 1 trigger.

Note: The field naming convention used below is a little awkward but it goes like - first 5 chars in field name correspond to table name, next 2 chars define data type, next 2 chars define Constraint, renaming letters are the name of field.

Table 1

• tbl_BinaryTree_Nodes, primary table to keep Node details (say member details)

Fields:

• Nodes_IN_PK_Code -- Primary Key of the table
• Nodes_IN_FK_ParentCode -- Parent node
• Nodes_CH_xx_Position -- Position under Parent node either Left Or Right
• Nodes_VC_xx_NodeData -- Node Data -(more fields can be added to accommodate Node Data

Table 2

• tbl_BinaryTree_Hierarchy, secondary table to keep Node hierarchy

Fields:

• Hiera_IN_PK_Code -- primary key of the table
• Hiera_IN_FK_ParentCode -- foreign key
• Hiera_IN_FK_ChildCode -- foreign key
• Hiera_CH_xx_Position -- Position under Parent node either Left Or Right
• Hiera_IN_xx_NodeLevel -- Node Level under tree

Trigger 1

trg_BinaryTree_Nodes_ADD, to update Tree hierarchy for later query

The SQL to create tables and trigger is as follows:

Create Table tbl_BinaryTree_Nodes
(
    Nodes_IN_PK_Code Int Identity(1,1) Constraint PK_Nodes Primary Key,
    Nodes_IN_FK_ParentCode Int Constraint _
	FK_Nodes_To_Nodes References tbl_BinaryTree_Nodes (Nodes_IN_PK_Code ),
    Nodes_CH_xx_Position Char(1) Not Null Constraint CH_Nodes_Position Check _
	(Nodes_CH_xx_Position = 'L' OR Nodes_CH_xx_Position = 'R'),
    Nodes_VC_xx_NodeData Varchar(50)
)
GO

Create Table tbl_BinaryTree_Hierarchy
(
    Hiera_IN_PK_Code Int Identity(1,1) Constraint PK_Hiera Primary Key,
    Hiera_IN_FK_ParentCode Int Constraint _
	FK_Hiera_Nodes_Parent References tbl_BinaryTree_Nodes(Nodes_IN_PK_Code ),
    Hiera_IN_FK_ChildCode Int Constraint FK_Hiera_Nodes_Child References _
	tbl_BinaryTree_Nodes(Nodes_IN_PK_Code ),
    Hiera_CH_xx_Position  Char(1) Not Null Constraint CH_Hiera_Position Check _
	(Hiera_CH_xx_Position = 'L' OR Hiera_CH_xx_Position = 'R'),
    Hiera_IN_xx_NodeLevel int
)
GO

Create Trigger trg_BinaryTree_Nodes_ADD
On tbl_BinaryTree_Nodes
For Insert
AS
Begin
    IF (@@RowCount=1)
        Begin
            Insert Into tbl_BinaryTree_Hierarchy
                (Hiera_IN_FK_ParentCode, Hiera_IN_FK_ChildCode, _
		Hiera_CH_xx_Position, Hiera_IN_xx_NodeLevel)
            Select (Case When Hiera_IN_FK_ParentCode Is Null _
		Then Hiera_IN_FK_ChildCode Else Hiera_IN_FK_ParentCode  End), 
                    (Select Nodes_IN_PK_Code From Inserted), _
			(Case When Hiera_IN_FK_ParentCode Is Null _
			Then (Select Nodes_CH_xx_Position From Inserted) _
			Else Hiera_CH_xx_Position End) , 
                    (Hiera_IN_xx_NodeLevel + 1 )
                From tbl_BinaryTree_Hierarchy Where Hiera_IN_FK_ChildCode = _
			(Select Nodes_IN_FK_ParentCode From Inserted)
            Union ALL
            Select NULL , Nodes_IN_PK_Code , Nodes_CH_xx_Position , 1 From Inserted 
        End
    Else
        Begin
            RaisError ('Multiple Insertion Not Handled in Trigger to _
				update tbl_BinaryTree_Hierarchy',1,1)
            -- Code Using Cursor for Multiple insert
            --... 
            --...
            --...
            --
        End
End
GO 

SQL Queries

We will populate the database with sample data for queries. We are going to create a Tree as shown below:

 --'------------------------------------------
--'          The Binary Tree Representation
--'------------------------------------------
--'                 RootNode
--'             --------|-------
--'             |              |
--'            AL1            AL2
--'       -----|-----
--'       |          |
--'      AL2        AR2
--'   ---|---
--'  |       |
--' AL3     AR3
--'------------------------------------------

The SQL to generate the above Tree is as given below:

Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
	Nodes_VC_xx_NodeData) Values(Null,'L','Root Node')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
	Nodes_VC_xx_NodeData) Values(1,'L','AL1')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
	Nodes_VC_xx_NodeData) Values(1,'R','AR1')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
	Nodes_VC_xx_NodeData) Values(2,'L','AL2')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
	Nodes_VC_xx_NodeData) Values(2,'R','AR2')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
	Nodes_VC_xx_NodeData) Values(4,'L','AL3')
GO
Insert Into tbl_BinaryTree_Nodes (Nodes_IN_FK_ParentCode, Nodes_CH_xx_Position, _
	Nodes_VC_xx_NodeData) Values(4,'R','AR3') 

-- A. Get All Nodes directly under current Node
Select B.Nodes_VC_xx_NodeData, Hiera_IN_xx_NodeLevel From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ChildCode  = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode=1 

-- B. Get All Nodes directly under current Node in left side
Select B.Nodes_VC_xx_NodeData, Hiera_IN_xx_NodeLevel From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ChildCode  = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode=1 And H.Hiera_CH_xx_Position ='L'

-- C. Get All Nodes directly under current Node in right side
Select B.Nodes_VC_xx_NodeData, Hiera_IN_xx_NodeLevel From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ChildCode  = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode=1 And H.Hiera_CH_xx_Position ='R'

-- D. Get All Nodes directly above the current 
Select B.Nodes_VC_xx_NodeData, Hiera_IN_xx_NodeLevel From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ParentCode  = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ChildCode=7

-- E. Get count of Nodes at each level under a specific node
Select Hiera_IN_xx_NodeLevel, count(*) From tbl_BinaryTree_Hierarchy H
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ChildCode  = B.Nodes_IN_PK_Code
Where H.Hiera_IN_FK_ParentCode=1 
Group By Hiera_IN_xx_NodeLevel

-- F. To find out the Nodes which got balanced due to new node entry
-- Lets us assume that the newly added node is AR3 - (which makes AL2 balanced)
-- We can use simple SQL Query or Common Table Expressions (CTE) 
-- on SQL 2005 to get the data
-- SQL Using Common Table Expressions (CTE) on SQL 2005
With CTE as (
Select B.Nodes_IN_PK_Code as PK, B.Nodes_VC_xx_NodeData as NodeData, _
	Hiera_IN_xx_NodeLevel as NodeLevel, 
      '' as IsBalanced,
   Power(2,Hiera_IN_xx_NodeLevel)-2 as TotalNodeForBalanceTree,
   (Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
	Where Hiera_CH_xx_Position = 'L' and _
	Hiera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) _
	as TotalLeftChild,
   (Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
	Where Hiera_CH_xx_Position = 'R' and _
	iera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) _
	as TotalRightChild
From tbl_BinaryTree_Hierarchy H 
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ParentCode   = B.Nodes_IN_PK_Code

Where H.Hiera_IN_FK_ParentCode   is NOT NULL and H.Hiera_IN_FK_ChildCode = 7   
					-- (Primary key of Newly Added Node) 
)
Select CTE.PK, CTE.NodeData, CTE.NodeLevel,
Case   When ((CTE.TotalNodeForBalanceTree / 2 = TotalLeftChild) and _
	(CTE.TotalNodeForBalanceTree / 2 = TotalRightChild)) then _
	'Yes' Else' No' End As IsBalanced, 
CTE.TotalNodeForBalanceTree , CTE.TotalLeftChild , CTE.TotalRightChild
From CTE 

Some More Queries - 2

• Download akyBinaryTreeSQLQuery - 5.56 KB

 --'------------------------------------------
--' TREE 2
--'  The Binary Tree Representation  Tree - 2 
--'------------------------------------------
--'                 RootNode
--'             --------|-------
--'             |              |
--'            AL              AR
--'       -----|-----      -----|-----
--'       |          |     |          |
--'      ZL         ZR     BL        BR
--'                      ---|---   ---|---
--'                     |       |  |      |
--'                    CL      CR  DL     *DR*
--'------------------------------------------ 

A. How To Find the Balanced Node due to New Node Entry (with Reference to Tree -2)

Let us assume that the newly added node is *DR* - (which makes AR, BR balanced).

We can use a simple SQL Query or Common Table Expressions (CTE) on SQL 2005 to get the data:

With CTE as (
Select B.Nodes_IN_PK_Code as PK, B.Nodes_VC_xx_NodeData as NodeData, _
	Hiera_IN_xx_NodeLevel as NodeLevel, 
      '' as IsBalanced,
   Power(2,Hiera_IN_xx_NodeLevel)-2 as TotalNodeForBalanceTree,
   (Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
	Where Hiera_CH_xx_Position = 'L' and _
	Hiera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) _
	as TotalLeftChild,
   (Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
	Where Hiera_CH_xx_Position = 'R' and _
	Hiera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) _
	as TotalRightChild
From tbl_BinaryTree_Hierarchy H 
Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ParentCode   = _
	B.Nodes_IN_PK_Code

Where H.Hiera_IN_FK_ParentCode   _
is NOT NULL and H.Hiera_IN_FK_ChildCode = 7   -- (Primary key of Newly Added Node) 
)
Select CTE.PK, CTE.NodeData, CTE.NodeLevel,
Case   When ((CTE.TotalNodeForBalanceTree / 2 = TotalLeftChild) and _
	(CTE.TotalNodeForBalanceTree / 2 = TotalRightChild)) then 'Yes' Else' No' _
	End As IsBalanced, 
CTE.TotalNodeForBalanceTree , CTE.TotalLeftChild , CTE.TotalRightChild
From CTE

B. Finding Extreme Left & Right Leaf of Node (with Reference to Tree -2)

To add new node below any node to either its extreme right or extreme left, you just need to know the last node (Leaf) in the corresponding side. This you can get using the simple SQL Query.

For example, in the Tree above, extreme right of root is *DR*, and extreme left is ZL. Similarly, extreme right of Node AR is *DR* and extreme Left is CL.

;with CTE (ExtremeNode, Position, NodeLevel  )As 
(
    Select Hiera_IN_FK_ChildCode, Hiera_CH_xx_Position, 1 from  tbl_BinaryTree_Hierarchy 
            where Hiera_IN_xx_NodeLevel=2 and Hiera_IN_FK_ParentCode = _
		?ParentNodePK?  and Hiera_CH_xx_Position = ?LegSide?
    UNION ALL
    Select Hiera_IN_FK_ChildCode, Hiera_CH_xx_Position , CTE.NodeLevel + 1   _
		from  tbl_BinaryTree_Hierarchy 
            INNER JOIN CTE  ON CTE.ExtremeNode = Hiera_IN_FK_ParentCode _
		and CTE.Position = Hiera_CH_xx_Position
            where Hiera_IN_xx_NodeLevel = 2

)
Select Top 1 *  From CTE order By NodeLevel Desc; 

C. To get Node List which became balanced nodes due to new insertion (with reference to Tree -2 and For MLM Commission Payment)

When *DR* is added, then BR & AR get paid - but how much is not clear - According to general MLM trend, we can figure out that BR will get benefit of 1 Pair, and AR will get benefit of 1 pair.

We need to find out the list of parent Nodes w.r.t. the newly added node which will get benefit.

Now to get the list of nodes that needs to be paid is as follows.

The SQL Query below will give you the list of all the parents with last column ShouldIPay (Pay or DoNotPay) indicating which parent node needs to be paid (modify field list according to need).

With CTE as (
  Select B.Nodes_IN_PK_Code as PK, B.Nodes_VC_xx_NodeData as NodeData, _
	Hiera_IN_xx_NodeLevel as NodeLevel, _
	Hiera_CH_xx_Position as Position, '' as IsBalanced,
    Power(2,Hiera_IN_xx_NodeLevel)-2 as TotalNodeForBalanceTree,
    (Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
	Where Hiera_CH_xx_Position = 'L' and _
	Hiera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) as TotalLeftChild,
    (Select Count(Hiera_IN_PK_Code) From tbl_BinaryTree_Hierarchy _
	Where Hiera_CH_xx_Position = 'R' and _
	Hiera_IN_FK_ParentCode=B.Nodes_IN_PK_Code) as TotalRightChild
  From tbl_BinaryTree_Hierarchy H 
  Left Outer Join tbl_BinaryTree_Nodes B on H.Hiera_IN_FK_ParentCode   = _
	B.Nodes_IN_PK_Code
  Where H.Hiera_IN_FK_ParentCode   is NOT NULL and _
	H.Hiera_IN_FK_ChildCode = ?PKofNewnode?   -- (Primary key of Newly Added Node) 
)
Select CTE.PK, CTE.NodeData, CTE.NodeLevel, CTE.Position,
Case   When ((CTE.TotalNodeForBalanceTree / 2 = TotalLeftChild) _
	and (CTE.TotalNodeForBalanceTree / 2 = TotalRightChild)) _
	then 'Yes' Else' No' End As IsBalanced, 
CTE.TotalNodeForBalanceTree , CTE.TotalLeftChild , CTE.TotalRightChild,
Case   When Position ='L' then (Case When TotalLeftChild<=TotalRightChild _
	Then 'PAY' Else 'Do Not Pay' End ) 
       When Position ='R' then (Case When TotalLeftChild>=TotalRightChild _
	Then 'PAY' Else 'Do Not Pay' End ) 
        End As ShouldIPay
From CTE 

The tables can be easily modified to keep additional information w.r.t. information of node, however the basic fields will remain the same.

Currently, the trigger is written for single insertion only, we can modify trigger to handle bulk insert. We have to write Trigger to handle Node shifting to modify hierarchy table.

History

• Revision 1: Some more queries - 2 sections added