Log in

The Job Interview: Technical questions (Pt. II)

By DimitriC at March 09, 2011 19:10
Filed Under: Programming, Training, tips & tricks

Let’s have a look at a binary tree. In my implementation of the binary tree, I use a property to keep track of the fact that the node in question is the root node (= the node where the tree begins), the Parent-property. This refers to the node that has the current node as one of it’s children (or leafs). You can of course browse through your entire tree to find the node that’s not referenced by any other node, but that will probably take a lot of checks, especially if you have a big binary tree. Even when it’s a small binary tree I would use this property. It makes it easier to navigate through the tree.

 

   1: public class BTNode
   2: {
   3:     public BTNode LeftNode { get; set; }
   4:     public BTNode RightNode { get; set; }
   5:     public BTNode Parent { get; set; }
   6:  
   7:     public int value;    
   8:  
   9:     public BTNode(int val)
  10:     {
  11:         this.value = val;
  12:     }
  13:  
  14:     public void AddNode(BTNode newNode)
  15:     {
  16:         newNode.Parent = this;
  17:  
  18:         if (newNode.value >= this.value)
  19:         {
  20:             if (RightNode == null)
  21:             {
  22:                 RightNode = newNode;
  23:             }
  24:             else
  25:             {
  26:                 RightNode.AddNode(newNode);
  27:             }
  28:         }
  29:         else
  30:         {
  31:             if (LeftNode == null)
  32:             {
  33:                 LeftNode = newNode;
  34:             }
  35:             else
  36:             {
  37:                 LeftNode.AddNode(newNode);
  38:             }
  39:         }
  40:     }
  41:  
  42:     public BTNode Search(int srchValue)
  43:     {
  44:         if (srchValue == this.value)
  45:         {
  46:             return this;
  47:         }
  48:  
  49:         if (srchValue >= this.value)
  50:         {
  51:             if (this.RightNode == null)
  52:             {
  53:                 return null;
  54:             }
  55:             else
  56:             {
  57:                 return this.RightNode.Search(srchValue);
  58:             }
  59:         }
  60:         else
  61:         {
  62:             if (this.LeftNode == null)
  63:             {
  64:                 return null;
  65:             }
  66:             else
  67:             {
  68:                 return this.LeftNode.Search(srchValue);
  69:             }
  70:         }
  71:     }
  72:  
  73:     public void Delete()
  74:     {
  75:         //bottom of tree
  76:         if (this.LeftNode == null && this.RightNode == null)
  77:         {
  78:             if (this.Parent.LeftNode.value == this.value)
  79:             {
  80:                 this.Parent.LeftNode = null;
  81:             }
  82:             else
  83:             {
  84:                 this.Parent.RightNode = null;
  85:             }
  86:         }
  87:  
  88:         //Middle of tree - RightNode
  89:         if (this.LeftNode == null && this.RightNode != null)
  90:         {
  91:             if (this.Parent.LeftNode.value == this.value)
  92:             {
  93:                 this.Parent.LeftNode = this.RightNode;
  94:             }
  95:             else
  96:             {
  97:                 this.Parent.RightNode = this.RightNode;
  98:             }
  99:         }
 100:  
 101:         //Middle of tree - LeftNode
 102:         if (this.LeftNode != null && this.RightNode == null)
 103:         {
 104:             if (this.Parent.LeftNode.value == this.value)
 105:             {
 106:                 this.Parent.LeftNode = this.LeftNode;
 107:             }
 108:             else
 109:             {
 110:                 this.Parent.RightNode = this.LeftNode;
 111:             }
 112:         }
 113:  
 114:         if (this.LeftNode != null && this.RightNode != null)
 115:         {
 116:             if (this.Parent == null)
 117:             {
 118:                 throw new ApplicationException("You can not delete the root node!");
 119:             }
 120:  
 121:             if (this.Parent.LeftNode.value == this.value)
 122:             {
 123:                 this.Parent.LeftNode = this.LeftNode;
 124:                 this.LeftNode.RightNode = this.RightNode;
 125:             }
 126:             else
 127:             {
 128:                 this.Parent.RightNode = this.RightNode;
 129:                 this.RightNode.LeftNode = this.LeftNode;
 130:             }
 131:         }
 132:     }

 

To use it, you instantiate a node and assign new BTNodes to the leaves. Wherever you are in the tree-structure, you’ll find it easy to search for nodes. Keep in mind that the AddNode and Delete only reflect on the current node.

Tags: , , , ,
Comments (0) E-mail Kick it! DZone it! del.icio.us Permalink Post RSS
Comments are closed