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
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 nodeNodes_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)
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')
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
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'
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'
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
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
Lets us assume that the newly added node is AR3 - (which makes AL2 balanced)
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
)
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
--'------------------------------------------
--' 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
)
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?
)
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
