none
Get next node in PreOrder Traversal without calling from a loop RRS feed

  • Question

  • I know it's straight forward to write the code for a pre order traversal of the Binary tree. My requirement is that I want to get Next node from any random node from the pre order traversed list. Note Next node should be fetched on demand basis and not necessarily from a foreach loop at caller side. Preferably this Next method needs to be an extension method and should be called on a given Node.

    I am thinking to use some sort of "yield" to maintain a state, but my restriction is that extension method's signature I can not modify. It should strictly return Node object and NOT IEnumerable.

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace ConsoleApp2
    {
        class Program
        {
            static void Main(string[] args)
            {
                var r = new Node(1,
                    new Node(2, null, null),
                    new Node(3, null, null));
    
                // I know I can do a preorder and get Next node one by one in a loop
                var list = new List<Node>();
                PreOrder(r, list);
                foreach (var item in list)
                {
                    Console.WriteLine(item.data);
                }
    
                // But I want to call it in following way. Note I can call Next on any random node of the tree.
                var next = r.Next();
                Console.WriteLine(next.data);
    
                next = next.Next();
                Console.WriteLine(next.data);
    
                next = next.Next();
                Console.WriteLine(next.data);
            }
            static void PreOrder(Node node, List<Node> list)
            {
                if (node == null) return;
                list.Add(node);
                PreOrder(node.left, list);
                PreOrder(node.right, list);
            }
        }
        public class Node
        {
            public Node left;
            public Node right;
            public int data;
    
            public Node(int d, Node l, Node r)
            {
                data = d;
                left = l;
                right = r;
            }
        }
        public static class NodeExtensions
        {
            public static Node Next(this Node node)
            {
                // I want to implement this
            }
        }
    }

    Saturday, April 4, 2020 8:22 AM

Answers

  • I think that you must add a new member — parent:

    public class Node

    {

       public Node parent;

       public Node left;

       public Node right;

       public int data;

       . . .

    }

     

    Make sure that it contains correct values, then try this function:

    public static class NodeExtensions

    {

       public static Node Next( this Node node )

       {

          if( node.left != null ) return node.left;

          if( node.right != null ) return node.right;

     

          var n = node;

     

          while( n.parent != null )

          {

             var p = n.parent;

             if( p.right != null && p.right != n ) return p.right;

             n = p;

          }

     

          return null;

       }

    }


    Saturday, April 4, 2020 9:50 AM