From Basic to Intermediate: Queues, Lists, and Trees (VII)

Introduction

In the previous article “From Basic to Intermediate: Queues, Lists, and Trees (VI)”, we showed how to implement a basic mechanism for building a tree. At the end of that article, we adapted the code to use a template, thereby generalizing the mechanism we had developed to some extent.

Although many people probably don't use trees actively, understanding the mechanisms underlying the implementation of this data structure will allow you to make better use of MQL5's capabilities. Remember that the main purpose here is educational. Therefore, each principle you adopt should be adapted to your specific goals and the particular circumstances of the situation. Although, in theory, everything implemented and demonstrated here may seem applicable to any situation, it’s possible that it won’t be the most suitable solution for your specific purpose. In that case, a clear understanding of the concepts presented and explained in the articles will help you find the best solution for your situation.

All right, based on this principle, we need to understand how to perform another type of operation on a tree. Although you probably won't use this implementation very often, understanding how it works can help you solve other types of problems as well. In this article, we will first focus on removing nodes from a binary tree.

If you think this is an easy task, you're right. However, if you don't understand certain concepts, this task—which, in my opinion, is relatively simple and easy to implement—could turn into a real headache, my dear reader. Especially if you're just starting to learn programming. Without further ado, let's move on to the main topic of this article.

Queues, Lists, and Trees (VII)

When it comes to removing nodes from a linked structure, many people encounter certain difficulties. However, unlike queues and lists, where removing a node is relatively simple, the situation is different with trees. Therefore, a precise understanding of what happens when a node is deleted from a tree can help you understand other aspects that we will cover later. This is because when deleting a node from a tree a rather curious situation arises: for a moment, the structure can be thought of as forming a second tree.

To understand how a node is deleted from a tree and what happens to its structure, you first need to understand the tree structure itself from the output generated in the terminal by the traversal functions. I know this might seem a little strange at first, and it may be hard to visualize in the first few tree examples you work through, so let's go through it all together, step by step. First of all, we need to analyze the code presented in the previous article, albeit with a slight modification. The complete code is shown below:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         void Seq(C_TreeNode *ptr, const E_SEQ type)
064.         {
065.             if (ptr == NULL) return;
066. 
067.             switch (type)
068.             {
069.                 case eInOrder   :
070.                 case ePostOrder :
071.                 case eDestroy   :
072.                     Seq((*ptr).GetLeft(), type);
073.                     if (type == eInOrder) break;
074.                     Seq((*ptr).GetRight(), type);
075.             }
076.             m_szInfo += def_InfoToString(ptr);
077.             switch (type)
078.             {
079.                 case ePreOrder  :
080.                     Seq((*ptr).GetLeft(), type);
081.                 case eInOrder   :
082.                     Seq((*ptr).GetRight(), type);
083.                     break;
084.                 case eDestroy   :
085.                     delete ptr;
086.             }
087.         }
088. //+----------------+
089.     public  :
090. //+----------------+
091.         C_Tree()
092.             :root(NULL)
093.         {}
094. //+----------------+
095.         ~C_Tree()
096.         {
097.             Seq(root, eDestroy);
098.         }
099. //+----------------+
100.         void Store(T info)
101.         {
102.             if (root == NULL) root = Insert(root, root, info);
103.             else Insert(root, root, info);
104.         }
105. //+----------------+
106.         string In_Order(void)
107.         {
108.             m_szInfo = "In Order: ";
109.             Seq(root, eInOrder);
110.             
111.             return m_szInfo;
112.         }
113. //+----------------+
114.         string Pre_Order(void)
115.         {
116.             m_szInfo = "Pre Order: ";
117.             Seq(root, ePreOrder);
118. 
119.             return m_szInfo;
120.         }
121. //+----------------+
122.         string Post_Order(void)
123.         {
124.             m_szInfo = "Post Order: ";
125.             Seq(root, ePostOrder);
126. 
127.             return m_szInfo;
128.         }
129. //+----------------+
130.     #undef def_InfoToString
131. //+----------------+
132. };
133. #undef C_TreeNode
134. //+------------------------------------------------------------------+
135. void OnStart(void)
136. {
137.     C_Tree <int> Tree;
138. 
139.     Tree.Store(10);
140.     Tree.Store(-6);
141.     Tree.Store(47);
142.     Tree.Store(35);
143.     Tree.Store(85);
144.     Tree.Store(40);
145. 
146.     Print(Tree.In_Order());
147.     Print(Tree.Pre_Order());
148.     Print(Tree.Post_Order());
149. }
150. //+------------------------------------------------------------------+

Code 01

Although the complete code is shown here, what we're really interested in is the structure created by the instructions between lines 139 and 144. Although the calls to the traversal functions between lines 146 and 148 generate output in a linear format, I need you, my dear and esteemed reader, to make a little effort and interpret it differently. This output should help you visualize the structure that the code creates. In some cases, we may end up with a structure similar to a linked list. However, because of the order in which the values were added, we will create a tree structure rather than a linear one. That's exactly what I want you to try to picture in your mind, because if you can't do that, you won't be able to understand how to delete a node from a tree without destroying the tree itself.

When you run Code 01, you will see the output shown in the following figure in the terminal:

Figure 01

Now, dear reader, I’d like you to focus on Figure 01 and, at the same time, mentally reconstruct how the Pre_Order and Post_Order functions generated the output shown in Figure 01. Why don't you mention the output generated by the In_Order function? The reason is simple, my dear reader. The In_Order function always produces output similar to that of a sorted linked list. Since this output isn't particularly helpful to us—at least in this case—we can ignore it.

All right, let's start by focusing on the output generated by the Post_Order function. This function first displays the leaf nodes and then the internal nodes of a tree. Keep the following in mind: YOU DON'T KNOW how many leaf nodes there are in a tree. All you know is that each node can point to at most two child nodes. Thus, we know with complete certainty that the first two nodes appearing in the output are leaf nodes, regardless of any other information, since the C_TreeNode class itself defines two possible pointers.

Now we need to look at the output generated by the Pre_Order function. In this case, the function begins its traversal at the root node and initially moves to the left until it finds a leaf node. Then it returns to the previous node and continues along the right branch. Based on this, we can already conclude that the root node contains the value 10, and the value -6 is stored in the leaf node located to the left of the root node. This gives us the figure shown below:

Figure 02

All right, now we have a partial picture of the tree that we can visualize in our minds. Now I need you to keep up this small effort. If you look closely at Figure 02, you will notice the following: the two known values shown there are part of a complete branch of the tree. What is missing can and should be interpreted as a new tree. If you can grasp this, you'll see that, according to the output generated by the Pre_Order function, the next node to be visited will be the root of this new tree we're imagining. I know this might seem strange, but you should try to visualize the structure in a nonlinear way.

All right, if Figure 02 shows the left branch, the root node contains the value 10, and the statement on line 54 defines how the nodes will be linked, then we can say that the next figure represents the next step in mentally constructing the tree created by Code 01.

Figure 03

So, that seems to make sense. However, we still need to fill in the remaining nodes in Figure 03. To do this, we'll once again use the output generated by the Post_Order function. Take note of this. The first value that appears in the output is -6, and the second value is 40. Why? Because the node that stores the value 40 is a leaf node. Wait a minute: if this is a leaf node, it can occupy any of the empty positions in Figure 03, right? Yes, my dear reader. However, you should study the code for the Post_Order function. Once you've done this, you'll see that Post_Order descends to the maximum possible depth before beginning to backtrack, and always traverses the left branch first, followed by the right. It is very important that you understand this point clearly, because if you change the order, the function will produce different output. Based on this, we can state with complete confidence that the following figure shows the position that the node with the value 40 should occupy.

Figure 04

All right, now we just need to place the two nodes in their correct positions. To determine where the nodes that store these values should be located, you can think about it for a moment or refer to Figure 01 itself. In both cases, we will end up with what is shown below, thereby completing the representation of our tree.

Figure 05

Great. If you understand how Figure 05 was obtained, then we can continue. However, before we do that, I want to show you a small detail. Suppose that the tree traversal is implemented in a different order, as shown in the following code snippet:

                   .
                   .
                   .
062. //+----------------+
063.         void Seq(C_TreeNode *ptr, const E_SEQ type)
064.         {
065.             if (ptr == NULL) return;
066. 
067.             switch (type)
068.             {
069.                 case ePostOrder :
070.                 case eDestroy   :
071.                     Seq((*ptr).GetRight(), type);
072.                 case eInOrder   :
073.                     Seq((*ptr).GetLeft(), type);
074.             }
075.             m_szInfo += def_InfoToString(ptr);
076.             switch (type)
077.             {
078.                 case eInOrder   :
079.                 case ePreOrder  :
080.                     Seq((*ptr).GetRight(), type);
081.                     if (type == eInOrder) break;
082.                     Seq((*ptr).GetLeft(), type);
083.                     break;
084.                 case eDestroy   :
085.                     delete ptr;
086.             }
087.         }
088. //+----------------+
                   .
                   .
                   .

Snippet 01

In this case, the code will generate the output shown in the following figure:

Figure 06

Note that, in this case, the simple change to Code 01 suggested in Snippet 01 resulted in the traversal output shown in Figure 06. Please also note that the difference between Snippet 01 and Code 01 is very subtle. It might have gone unnoticed if it had not been shown here in the article. Now you know, my dear reader: whenever you analyze output of this type, also try to examine the source code to get a more complete picture of the situation.

Great, now we can understand how a node is removed from a tree. I am confident that you, my dear reader, will be able to correctly interpret the output produced in the terminal. However, just to demonstrate very simply how to remove a node from a tree, we will first remove the node with a value of 47. The tree structure will then look as shown in the following figure.

Figure 07

Wow, that's actually pretty alarming, because we have a root node with a value of 10, a disconnected subtree whose root node has a value of 35, and an isolated node with a value of 85. That is exactly what the structure will look like, my dear reader, if we remove the node with a value of 47 without taking any precautions or applying any criterion.

How do we find the node in the tree that stores the value 47? You haven't explained yet how it's done. Hmm, that's true. I haven't yet explained how to find a node based on the value it contains. That was my oversight. Please forgive me, my dear reader. Before we begin the deletion process, let's take a look at how to find a specific node based on the value it contains. Searching is very simple: we just need to add a little code to the `Seq` method, whose definition begins on line 63. To do this, we'll use the complete code shown below:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy, eSearch};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         C_TreeNode *Seq(C_TreeNode *ptr, const E_SEQ type, const T info = 0)
064.         {
065.             if (ptr == NULL) return NULL;
066. 
067.             switch (type)
068.             {
069.                 case eSearch    :
070.                     while ((ptr != NULL) && ((*ptr).GetInfo() != info))
071.                         ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight());
072.                     return ptr;
073.                 case eInOrder   :
074.                 case ePostOrder :
075.                 case eDestroy   :
076.                     Seq((*ptr).GetLeft(), type);
077.                     if (type == eInOrder) break;
078.                     Seq((*ptr).GetRight(), type);
079.             }
080.             m_szInfo += def_InfoToString(ptr);
081.             switch (type)
082.             {
083.                 case ePreOrder  :
084.                     Seq((*ptr).GetLeft(), type);
085.                 case eInOrder   :
086.                     Seq((*ptr).GetRight(), type);
087.                     break;
088.                 case eDestroy   :
089.                     delete ptr;
090.             }
091. 
092.             return NULL;
093.         }
094. //+----------------+
095.     public  :
096. //+----------------+
097.         C_Tree()
098.             :root(NULL)
099.         {}
100. //+----------------+
101.         ~C_Tree()
102.         {
103.             Seq(root, eDestroy);
104.         }
105. //+----------------+
106.         void Store(T info)
107.         {
108.             if (root == NULL) root = Insert(root, root, info);
109.             else Insert(root, root, info);
110.         }
111. //+----------------+
112.         string In_Order(void)
113.         {
114.             m_szInfo = "In Order: ";
115.             Seq(root, eInOrder);
116.             
117.             return m_szInfo;
118.         }
119. //+----------------+
120.         string Pre_Order(void)
121.         {
122.             m_szInfo = "Pre Order: ";
123.             Seq(root, ePreOrder);
124. 
125.             return m_szInfo;
126.         }
127. //+----------------+
128.         string Post_Order(void)
129.         {
130.             m_szInfo = "Post Order: ";
131.             Seq(root, ePostOrder);
132. 
133.             return m_szInfo;
134.         }
135. //+----------------+
136.         void Address(const T info)
137.         {
138.             Print(info, " information address is: ", Seq(root, eSearch, info));
139.         }
140. //+----------------+
141.     #undef def_InfoToString
142. //+----------------+
143. };
144. #undef C_TreeNode
145. //+------------------------------------------------------------------+
146. void OnStart(void)
147. {
148.     C_Tree <int> Tree;
149. 
150.     Tree.Store(10);
151.     Tree.Store(-6);
152.     Tree.Store(47);
153.     Tree.Store(35);
154.     Tree.Store(85);
155.     Tree.Store(40);
156. 
157.     Print(Tree.In_Order());
158.     Print(Tree.Pre_Order());
159.     Print(Tree.Post_Order());
160.     Tree.Address(47);
161. }
162. //+------------------------------------------------------------------+

Code 02

Please note that Code 02 is almost identical to Code 01. Essentially, the declaration on line 40 introduces a new enumeration, and the `Seq` method—whose definition begins on line 63—is no longer a method with no return value and instead returns the address of the found node.

There is one point in this method that is important to understand, my dear reader: the conditional expression checked by the `while` loop, located on line 70. Many people, especially those who are just starting out, don't fully understand how a compiler works. I may explain this in detail in the future. I'm still thinking about it. Perhaps many people would be interested in learning about this, although I'm not sure yet whether it's worth raising this topic at all. If you're interested in this, please mention it in the comments on the article. If there is enough interest, I'll try to explain this in as much detail as possible. And I will do so with a practical approach, using only MQL5.

One more point worth mentioning: the conditional expression on line 71 follows the same logic used when inserting nodes into the tree. Please note that here, the values are compared using the same criterion as in the insertion statement shown on line 59. It's important to understand this because we need to follow the same traversal criterion so we don't get lost in the tree.

Let's continue, because I want to explain one detail of the conditional expression checked by the `while` loop and located on line 70. We're not interested in the loop itself; what matters is the condition expressed in this check.

Pay very close attention, because what I'm about to show you could drive any programmer crazy—though some more than others. Note the following: when the call to `Address` is executed on line 160, this method—whose definition begins on line 136—will be called. In turn, `Address` will call the `Seq` method—the definition of which begins on line 63—to retrieve the address of the node that stores the value passed as an argument. So far, so good. Indeed, when you run this code, you'll see the result shown below:

Figure 08

Now the most interesting part begins. Open the editor and, in Code 02 shown in the attachment, replace the value used as the search criterion with another value that is not stored in any node of the tree. For example, use 50 as the search value. The result will be as shown below:

Figure 09

So far, everything is correct. There's no problem here. Now replace the condition on line 70:

while (((*ptr).GetInfo() != info) && (ptr != NULL))

Recompile Code 02, changing only the condition on line 70. When you try to run it, you'll see the output shown in the following figure:

Figure 10

What happened? Well, that doesn't make any sense. You must be joking, because I've never seen anything like that. The condition on line 70 barely changed, and yet the code crashed? That's crazy. Well, my dear reader, even if it seems to you that this condition hasn't changed, that's actually not the case. This is due to certain characteristics of the compilation process. It's quite difficult to explain this in theory, but if you look at how the compiler works in practice, everything becomes clear. So, if you want to learn more about this, be sure to write in the comments section of this article: “I want to understand how the compiler works.” That way, I'll know whether it's worth writing a few articles to explain this in detail.

Let's get back to our topic. Thanks to the `Address` method, whose definition begins on line 136, we already have a mechanism for searching for a node based on the value it contains. It's time to implement the code that will remove a node from a tree.

To do this, we'll need to implement a deletion mechanism, which may seem a bit confusing at first. However, if you understood the beginning of this article, you'll have no trouble figuring out what we're going to do. Since I don't want to complicate the deletion mechanism right away, and deleting nodes from a tree is different from deleting nodes from a list, let's start with the simplest case. Next, we can consider a slightly more complex—and therefore more general—case. The simplest case is deleting a leaf from the tree. What does it mean for a node to be a leaf? You've explained what a node, a branch, and a root are.

However, you didn't say anything about leaf nodes. Well, in my opinion, the concept of a “leaf” should be fairly intuitive. In any case, let's clarify what that means. A leaf is a leaf node—that is, a node from which no branches extend. Essentially, this is the point where the branch we're following ends. To make this even clearer, Figure 05 shows three leaves: nodes with values of -6, 40, and 85. I think you understand what a leaf is by now.

All right, that's the simplest case. In theory, all we need to do is remove this node from the tree. However, in practice, it is not enough to simply free the memory occupied by this leaf. Before deleting a leaf, you must update the parent node's pointer that points to that leaf. Otherwise, during subsequent searches or traversals, the program will attempt to follow a reference containing an invalid memory address, and the code will terminate with an error.

“How come? I don't understand what you mean." Don't worry, dear reader; you'll understand everything soon enough. First, let's implement the code that will allow us to delete the tree's leaves. Below is a complete code example:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy, eSearch};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         C_TreeNode *Seq(C_TreeNode *ptr, const E_SEQ type, const T info = 0)
064.         {
065.             if (ptr == NULL) return NULL;
066. 
067.             switch (type)
068.             {
069.                 case eSearch    :
070.                     while ((ptr != NULL) && ((*ptr).GetInfo() != info))
071.                         ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight());
072.                     return ptr;
073.                 case eInOrder   :
074.                 case ePostOrder :
075.                 case eDestroy   :
076.                     Seq((*ptr).GetLeft(), type);
077.                     if (type == eInOrder) break;
078.                     Seq((*ptr).GetRight(), type);
079.             }
080.             m_szInfo += def_InfoToString(ptr);
081.             switch (type)
082.             {
083.                 case ePreOrder  :
084.                     Seq((*ptr).GetLeft(), type);
085.                 case eInOrder   :
086.                     Seq((*ptr).GetRight(), type);
087.                     break;
088.                 case eDestroy   :
089.                     delete ptr;
090.             }
091. 
092.             return NULL;
093.         }
094. //+----------------+
095.     public  :
096. //+----------------+
097.         C_Tree()
098.             :root(NULL)
099.         {}
100. //+----------------+
101.         ~C_Tree()
102.         {
103.             Seq(root, eDestroy);
104.         }
105. //+----------------+
106.         void Store(T info)
107.         {
108.             if (root == NULL) root = Insert(root, root, info);
109.             else Insert(root, root, info);
110.         }
111. //+----------------+
112.         string In_Order(void)
113.         {
114.             m_szInfo = "In Order: ";
115.             Seq(root, eInOrder);
116.             
117.             return m_szInfo;
118.         }
119. //+----------------+
120.         string Pre_Order(void)
121.         {
122.             m_szInfo = "Pre Order: ";
123.             Seq(root, ePreOrder);
124. 
125.             return m_szInfo;
126.         }
127. //+----------------+
128.         string Post_Order(void)
129.         {
130.             m_szInfo = "Post Order: ";
131.             Seq(root, ePostOrder);
132. 
133.             return m_szInfo;
134.         }
135. //+----------------+
136.         void DeleteNode(const T info)
137.         {
138.             C_TreeNode *tmp, *ptr = root;
139. 
140.             for (tmp = NULL; (ptr != NULL) && ((*ptr).GetInfo() != info); tmp = ptr, ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight()));
141. 
142.             if (ptr != NULL)
143.             {
144.                 if ((*ptr).GetLeft() == (*ptr).GetRight())
145.                 {
146.                     if (info < (*tmp).GetInfo()) (*tmp).SetLeft(NULL);
147.                     else (*tmp).SetRight(NULL);
148.                     delete ptr;
149.                 }
150.             }
151.         }
152. //+----------------+
153.     #undef def_InfoToString
154. //+----------------+
155. };
156. #undef C_TreeNode
157. //+------------------------------------------------------------------+
158. void OnStart(void)
159. {
160.     C_Tree <int> Tree;
161. 
162.     Tree.Store(10);
163.     Tree.Store(-6);
164.     Tree.Store(47);
165.     Tree.Store(35);
166.     Tree.Store(85);
167.     Tree.Store(40);
168. 
169.     Print(Tree.In_Order());
170.     Print(Tree.Pre_Order());
171.     Print(Tree.Post_Order());
172. 
173.     Tree.DeleteNode(85);
174.     Print("----------------");
175. 
176.     Print(Tree.In_Order());
177.     Print(Tree.Pre_Order());
178.     Print(Tree.Post_Order());
179. }
180. //+------------------------------------------------------------------+

Code 03

Nodes can be removed in various ways—both using recursion and using iterative approaches. In this case, we will use an iterative approach. The reason is that this approach is slightly faster, primarily because removing nodes can very quickly cause a tree to become unbalanced. The resulting structural degradation reduces the efficiency of the recursive traversals used to remove nodes. Let's take a look at what we're doing in Code 03.

When the DeleteNode call on line 173 is executed, the DeleteNode method—the definition of which begins on line 136—will be called. Within this method, the search loop will traverse a tree until it finds a node whose value matches the argument passed to it. Why don't we use the search performed by the Seq method? Because `Seq` returns the address of the found node but does not store a pointer to its parent node. The `DeleteNode` method requires both references in order to update the pointer in the parent node that points to the node to be deleted.

Please note the following, my dear reader. The loop, which begins on line 140, will compare the value stored in each node with the target value until it finds the node we want to remove. On each iteration, the assignment to the `tmp` variable will store the pointer to the node visited in the previous iteration; once the search is complete, this will be the parent node of the found node. When the search is complete, the condition on line 144 will check whether the found node is a leaf. In this case, the assignment on line 146 will change the left or right pointer of the parent node so that it no longer points to the leaf node being deleted. Finally, the `delete` operator on line 148 will free the memory occupied by this leaf.

Therefore, when we run Code 03, we will get the output shown below:

Figure 11

Now take a look at one detail in Figure 11—specifically, the part I've highlighted. If you look closely, you'll notice that the node that stored the value passed as an argument in the call on line 173 is missing from this highlighted area. This confirms that the assignment severed the link between the parent node and the deleted leaf, and that the `delete` statement freed the memory occupied by that leaf. It's important for you to notice this, because using the same technique shown in Code 03, we'll be able to remove almost all of the tree's nodes, leaf by leaf. And I say “almost” because there’s a problem when the root node is deleted. If you try to delete it using Code 03, even if it is the only node in the tree, the code will inevitably fail with an error. This is because the assignment on line 146 attempts to access the supposed parent node of the root via an invalid reference. To solve this problem, we need to add a condition that will prevent such access.

So now that you understand the logic behind the deletion code and the need to keep a pointer to the parent node of the node being deleted, we can restructure the code to make it clearer and more useful from both a practical and educational standpoint. So don't be alarmed by what we're about to see, my dear reader. I just don't want to break down the code block by block, because that would make the explanation pretty tedious.

After making all the necessary changes, we end up with the code shown below, which will be our new code for building trees:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         C_TreeNode *EraseAndMerge(C_TreeNode *ptr)
064.         {
065.             C_TreeNode *tmp = ptr;
066. 
067.             if ((*tmp).GetRight() == NULL) ptr = (*ptr).GetLeft();
068.             else if ((*tmp).GetLeft() == NULL) ptr = (*ptr).GetRight();
069.             else
070.             {
071.                 tmp = (*ptr).GetLeft();
072.                 while ((*tmp).GetRight() != NULL) tmp = (*tmp).GetRight();
073.                 (*tmp).SetRight((*ptr).GetRight());
074.                 tmp = ptr;
075.                 ptr = (*ptr).GetLeft();
076.             }
077.             delete tmp;
078. 
079.             return ptr;
080.         }
081. //+----------------+
082.         void Seq(C_TreeNode *ptr, const E_SEQ type)
083.         {
084.             if (ptr == NULL) return;
085. 
086.             switch (type)
087.             {
088.                 case eInOrder   :
089.                 case ePostOrder :
090.                 case eDestroy   :
091.                     Seq((*ptr).GetLeft(), type);
092.                     if (type == eInOrder) break;
093.                     Seq((*ptr).GetRight(), type);
094.             }
095.             m_szInfo += def_InfoToString(ptr);
096.             switch (type)
097.             {
098.                 case ePreOrder  :
099.                     Seq((*ptr).GetLeft(), type);
100.                 case eInOrder   :
101.                     Seq((*ptr).GetRight(), type);
102.                     break;
103.                 case eDestroy   :
104.                     delete ptr;
105.             }
106.         }
107. //+----------------+
108.     public  :
109. //+----------------+
110.         C_Tree()
111.             :root(NULL)
112.         {}
113. //+----------------+
114.         ~C_Tree()
115.         {
116.             Seq(root, eDestroy);
117.         }
118. //+----------------+
119.         void Store(T info)
120.         {
121.             if (root == NULL) root = Insert(root, root, info);
122.             else Insert(root, root, info);
123.         }
124. //+----------------+
125.         string In_Order(void)
126.         {
127.             m_szInfo = "In Order: ";
128.             Seq(root, eInOrder);
129.             
130.             return m_szInfo;
131.         }
132. //+----------------+
133.         string Pre_Order(void)
134.         {
135.             m_szInfo = "Pre Order: ";
136.             Seq(root, ePreOrder);
137. 
138.             return m_szInfo;
139.         }
140. //+----------------+
141.         string Post_Order(void)
142.         {
143.             m_szInfo = "Post Order: ";
144.             Seq(root, ePostOrder);
145. 
146.             return m_szInfo;
147.         }
148. //+----------------+
149.         void DeleteNode(const T info)
150.         {
151.             C_TreeNode *tmp, *ptr = root;
152. 
153.             for (tmp = NULL; (ptr != NULL) && ((*ptr).GetInfo() != info); tmp = ptr, ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight()));
154. 
155.             if (ptr != NULL)
156.             {
157.                 if (ptr == root) root = EraseAndMerge(ptr); else
158.                 {
159.                     if ((*tmp).GetLeft() == ptr) (*tmp).SetLeft(EraseAndMerge(ptr));
160.                     else (*tmp).SetRight(EraseAndMerge(ptr));
161.                 }
162.             }
163.         }
164. //+----------------+
165.     #undef def_InfoToString
166. //+----------------+
167. };
168. #undef C_TreeNode
169. //+------------------------------------------------------------------+
170. void OnStart(void)
171. {
172.     C_Tree <int> Tree;
173. 
174.     Tree.Store(10);
175.     Tree.Store(-6);
176.     Tree.Store(47);
177.     Tree.Store(35);
178.     Tree.Store(85);
179.     Tree.Store(40);
180. 
181.     Print(Tree.In_Order());
182.     Print(Tree.Pre_Order());
183.     Print(Tree.Post_Order());
184. 
185.     Tree.DeleteNode(10);
186.     Print("----------------");
187. 
188.     Print(Tree.In_Order());
189.     Print(Tree.Pre_Order());
190.     Print(Tree.Post_Order());
191. }
192. //+------------------------------------------------------------------+

Code 04

Please note that in Code 04, included in the code listing below, I removed the part related to searching the tree. This is because we will look at this topic in more detail another time. However, you may have noticed that I added a new method to the C_Tree class, the definition of which begins on line 63. Now pay close attention, my dear reader. The new method will be responsible for detaching the node to be removed and reconnecting the subtrees that depended on that node. This method uses virtually the same logic as in the code snippet above, which was used to delete a leaf. However, here I will show all the steps at once, since explaining them one by one would be too tedious and difficult.

The operation involves disconnecting the node selected for removal and then reconnecting the subtrees that depended on the selected node. No matter which node we're going to remove, the sequence of steps will always be the same. First, we isolate the selected node. Next, we update the necessary pointers to connect the remaining subtrees to each other and take the deleted node’s place in the structure. Finally, we free the memory occupied by the deleted node.

So, this is precisely the key point: the restructuring method is not executed on its own. The method that identifies the node to be removed calls the restructuring method. So, let's move on to the deletion method, the definition of which begins on line 149. Please note that the deletion method generally retains the same logic; we've only changed a few details. Please note that the condition on line 157 will now check whether the node selected for deletion is the root of the tree. In this case, the restructuring method will detach the current root, reconnect its subtrees, and set the node selected by the algorithm as the new root.

If the node selected for deletion is not the root, we will check whether the left or right pointer of the parent node points to the selected node. Next, we will update the corresponding pointer so that it points to the node that will occupy the structural position of the removed node. In a way, this is very similar to what we did when implementing node deletion in linked lists. As you can see, it's very simple and quite practical. As I mentioned at the beginning of the article, the node deletion code itself is quite simple. However, it's not that easy to understand how it works. That's why we had to go through all these steps before we got to Code 04.

So, what output does Code 04 produce? You can see it below:

Figure 12

Now, pay very close attention, and if you have any doubts, go back to the beginning of the article to understand what I'm about to explain. This tree, which you can see in Figure 12, has no branches on the left. This is because it is now completely unbalanced, which reduces search performance in the tree. However, you can clearly see that the node that was the original root has been replaced by the single node that formed the left branch of the original root. Since the replacement node took the place of the root, and there were no other nodes in the original left branch, the new root has no left branch.

Concluding Thoughts

In this article, we have clearly demonstrated and explained how to remove a node from a tree. This process tends to confuse beginners rather than help them understand how it’s done and why it needs to be done that way.

Since the purpose here is purely educational, the node deletion code was implemented using one of the many algorithms designed to solve problems of this type. Readers should also explore other mechanisms that can be used to delete nodes, since—depending on the number of branches each node has—the mechanism described in this article may not be the most appropriate. For such cases, there are other methods—ones that are much simpler and yield better results, at least in terms of execution speed.

Remember, dear reader: operations such as deleting and inserting nodes in a tree can cause it to become unbalanced. In some situations, this makes sense. However, in many other cases, an unbalanced tree reduces search efficiency within this structure. For this reason, I removed the part of the code responsible for searching the tree. In the next article, we'll take a closer look at this topic. Then you'll be able to decide which type of solution is most appropriate in each specific case.

MQ5 file	Description
Code 01	Simple Tree
Code 02	Simple Tree
Code 03	Simple Tree