Identifying Binary Search Trees from their Prufer Sequence












3












$begingroup$


If you ignore its root, a Binary Search Tree generated by some permutation of ${1, ldots, n}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found that there are A000245 distinct Prufer sequences.



import itertools

def generate_tree(l):
'''Return the root and a set of edges'''
if len(l) == 0:
return None, None
if len(l) == 1:
return l[0], set()
left_root, left_edges = generate_tree([x for x in l if x < l[0]])
right_root, right_edges = generate_tree([x for x in l if x > l[0]])
edges = set()
if left_root is not None:
edges.add((left_root, l[0]))
edges.update(left_edges)
if right_root is not None:
edges.add((l[0], right_root))
edges.update(right_edges)
return l[0], edges

def pruffer_sequence(edge_set):
degrees = {}
for v1, v2 in edge_set:
degrees[v1] = degrees.get(v1, 0) + 1
degrees[v2] = degrees.get(v2, 0) + 1
r =
while len(edge_set) > 1:
smallest_leaf = min([v for v in degrees.keys() if degrees[v] == 1])
degrees[smallest_leaf] -= 1
for e in edge_set:
if smallest_leaf in e:
edge_set = edge_set - {e}
neighbor = [v for v in e if v != smallest_leaf][0]
degrees[neighbor] -= 1
r.append(neighbor)
break
return r

for number_of_vertices in range(2, 10):
R = set()
for l in itertools.permutations(range(number_of_vertices)):
root, edge_set = generate_tree(l)
R.add( tuple( pruffer_sequence(edge_set) ))
print number_of_vertices, len(R)


Is there some way to characterize a BST by its Prufer sequence without first calculating its tree?










share|cite|improve this question









$endgroup$

















    3












    $begingroup$


    If you ignore its root, a Binary Search Tree generated by some permutation of ${1, ldots, n}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found that there are A000245 distinct Prufer sequences.



    import itertools

    def generate_tree(l):
    '''Return the root and a set of edges'''
    if len(l) == 0:
    return None, None
    if len(l) == 1:
    return l[0], set()
    left_root, left_edges = generate_tree([x for x in l if x < l[0]])
    right_root, right_edges = generate_tree([x for x in l if x > l[0]])
    edges = set()
    if left_root is not None:
    edges.add((left_root, l[0]))
    edges.update(left_edges)
    if right_root is not None:
    edges.add((l[0], right_root))
    edges.update(right_edges)
    return l[0], edges

    def pruffer_sequence(edge_set):
    degrees = {}
    for v1, v2 in edge_set:
    degrees[v1] = degrees.get(v1, 0) + 1
    degrees[v2] = degrees.get(v2, 0) + 1
    r =
    while len(edge_set) > 1:
    smallest_leaf = min([v for v in degrees.keys() if degrees[v] == 1])
    degrees[smallest_leaf] -= 1
    for e in edge_set:
    if smallest_leaf in e:
    edge_set = edge_set - {e}
    neighbor = [v for v in e if v != smallest_leaf][0]
    degrees[neighbor] -= 1
    r.append(neighbor)
    break
    return r

    for number_of_vertices in range(2, 10):
    R = set()
    for l in itertools.permutations(range(number_of_vertices)):
    root, edge_set = generate_tree(l)
    R.add( tuple( pruffer_sequence(edge_set) ))
    print number_of_vertices, len(R)


    Is there some way to characterize a BST by its Prufer sequence without first calculating its tree?










    share|cite|improve this question









    $endgroup$















      3












      3








      3


      1



      $begingroup$


      If you ignore its root, a Binary Search Tree generated by some permutation of ${1, ldots, n}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found that there are A000245 distinct Prufer sequences.



      import itertools

      def generate_tree(l):
      '''Return the root and a set of edges'''
      if len(l) == 0:
      return None, None
      if len(l) == 1:
      return l[0], set()
      left_root, left_edges = generate_tree([x for x in l if x < l[0]])
      right_root, right_edges = generate_tree([x for x in l if x > l[0]])
      edges = set()
      if left_root is not None:
      edges.add((left_root, l[0]))
      edges.update(left_edges)
      if right_root is not None:
      edges.add((l[0], right_root))
      edges.update(right_edges)
      return l[0], edges

      def pruffer_sequence(edge_set):
      degrees = {}
      for v1, v2 in edge_set:
      degrees[v1] = degrees.get(v1, 0) + 1
      degrees[v2] = degrees.get(v2, 0) + 1
      r =
      while len(edge_set) > 1:
      smallest_leaf = min([v for v in degrees.keys() if degrees[v] == 1])
      degrees[smallest_leaf] -= 1
      for e in edge_set:
      if smallest_leaf in e:
      edge_set = edge_set - {e}
      neighbor = [v for v in e if v != smallest_leaf][0]
      degrees[neighbor] -= 1
      r.append(neighbor)
      break
      return r

      for number_of_vertices in range(2, 10):
      R = set()
      for l in itertools.permutations(range(number_of_vertices)):
      root, edge_set = generate_tree(l)
      R.add( tuple( pruffer_sequence(edge_set) ))
      print number_of_vertices, len(R)


      Is there some way to characterize a BST by its Prufer sequence without first calculating its tree?










      share|cite|improve this question









      $endgroup$




      If you ignore its root, a Binary Search Tree generated by some permutation of ${1, ldots, n}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found that there are A000245 distinct Prufer sequences.



      import itertools

      def generate_tree(l):
      '''Return the root and a set of edges'''
      if len(l) == 0:
      return None, None
      if len(l) == 1:
      return l[0], set()
      left_root, left_edges = generate_tree([x for x in l if x < l[0]])
      right_root, right_edges = generate_tree([x for x in l if x > l[0]])
      edges = set()
      if left_root is not None:
      edges.add((left_root, l[0]))
      edges.update(left_edges)
      if right_root is not None:
      edges.add((l[0], right_root))
      edges.update(right_edges)
      return l[0], edges

      def pruffer_sequence(edge_set):
      degrees = {}
      for v1, v2 in edge_set:
      degrees[v1] = degrees.get(v1, 0) + 1
      degrees[v2] = degrees.get(v2, 0) + 1
      r =
      while len(edge_set) > 1:
      smallest_leaf = min([v for v in degrees.keys() if degrees[v] == 1])
      degrees[smallest_leaf] -= 1
      for e in edge_set:
      if smallest_leaf in e:
      edge_set = edge_set - {e}
      neighbor = [v for v in e if v != smallest_leaf][0]
      degrees[neighbor] -= 1
      r.append(neighbor)
      break
      return r

      for number_of_vertices in range(2, 10):
      R = set()
      for l in itertools.permutations(range(number_of_vertices)):
      root, edge_set = generate_tree(l)
      R.add( tuple( pruffer_sequence(edge_set) ))
      print number_of_vertices, len(R)


      Is there some way to characterize a BST by its Prufer sequence without first calculating its tree?







      combinatorics trees






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Jan 27 '15 at 3:10









      ybermanyberman

      1,496714




      1,496714






















          1 Answer
          1






          active

          oldest

          votes


















          1












          $begingroup$

          Is there a reason you chose to take the BST of the permutations? There are multiple ways to uniquely represent a permutation as a tree, where you would end up with $n!$ different Prufer sequences. Categorizing such sequences might be more interesting.



          But in any case, I couldn't find a way to enumerate without iterating all the $n!$ permutations. I tried to find a bijection between Prufer sequences and something counted by the difference of Catalan numbers $C_n-C_{n-1}$, but to no avail. I was however, able to speed up your code.



          Given two permutations $p_1, p_2 in S_n$



          $$ text{Prufer}(p_1) ;;;= ;;; text{Prufer}(p_2) \
          Longleftrightarrow \
          text{Tree}(p_1) ;;; = ;;; text{Tree}(p_2) \
          Longleftrightarrow \
          text{Edges}(text{BST}(p_1)) ;;; = ;;; text{Edges}(text{BST}(p_2)) \
          $$

          So you only need to find the Prufer sequence when you come across a new edge set. Also, if you actually construct the BST, you can find the Prufer sequence in linear time. Here is my python code (takes 6 seconds rather than 18).






          share|cite|improve this answer











          $endgroup$














            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "69"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1121288%2fidentifying-binary-search-trees-from-their-prufer-sequence%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            1












            $begingroup$

            Is there a reason you chose to take the BST of the permutations? There are multiple ways to uniquely represent a permutation as a tree, where you would end up with $n!$ different Prufer sequences. Categorizing such sequences might be more interesting.



            But in any case, I couldn't find a way to enumerate without iterating all the $n!$ permutations. I tried to find a bijection between Prufer sequences and something counted by the difference of Catalan numbers $C_n-C_{n-1}$, but to no avail. I was however, able to speed up your code.



            Given two permutations $p_1, p_2 in S_n$



            $$ text{Prufer}(p_1) ;;;= ;;; text{Prufer}(p_2) \
            Longleftrightarrow \
            text{Tree}(p_1) ;;; = ;;; text{Tree}(p_2) \
            Longleftrightarrow \
            text{Edges}(text{BST}(p_1)) ;;; = ;;; text{Edges}(text{BST}(p_2)) \
            $$

            So you only need to find the Prufer sequence when you come across a new edge set. Also, if you actually construct the BST, you can find the Prufer sequence in linear time. Here is my python code (takes 6 seconds rather than 18).






            share|cite|improve this answer











            $endgroup$


















              1












              $begingroup$

              Is there a reason you chose to take the BST of the permutations? There are multiple ways to uniquely represent a permutation as a tree, where you would end up with $n!$ different Prufer sequences. Categorizing such sequences might be more interesting.



              But in any case, I couldn't find a way to enumerate without iterating all the $n!$ permutations. I tried to find a bijection between Prufer sequences and something counted by the difference of Catalan numbers $C_n-C_{n-1}$, but to no avail. I was however, able to speed up your code.



              Given two permutations $p_1, p_2 in S_n$



              $$ text{Prufer}(p_1) ;;;= ;;; text{Prufer}(p_2) \
              Longleftrightarrow \
              text{Tree}(p_1) ;;; = ;;; text{Tree}(p_2) \
              Longleftrightarrow \
              text{Edges}(text{BST}(p_1)) ;;; = ;;; text{Edges}(text{BST}(p_2)) \
              $$

              So you only need to find the Prufer sequence when you come across a new edge set. Also, if you actually construct the BST, you can find the Prufer sequence in linear time. Here is my python code (takes 6 seconds rather than 18).






              share|cite|improve this answer











              $endgroup$
















                1












                1








                1





                $begingroup$

                Is there a reason you chose to take the BST of the permutations? There are multiple ways to uniquely represent a permutation as a tree, where you would end up with $n!$ different Prufer sequences. Categorizing such sequences might be more interesting.



                But in any case, I couldn't find a way to enumerate without iterating all the $n!$ permutations. I tried to find a bijection between Prufer sequences and something counted by the difference of Catalan numbers $C_n-C_{n-1}$, but to no avail. I was however, able to speed up your code.



                Given two permutations $p_1, p_2 in S_n$



                $$ text{Prufer}(p_1) ;;;= ;;; text{Prufer}(p_2) \
                Longleftrightarrow \
                text{Tree}(p_1) ;;; = ;;; text{Tree}(p_2) \
                Longleftrightarrow \
                text{Edges}(text{BST}(p_1)) ;;; = ;;; text{Edges}(text{BST}(p_2)) \
                $$

                So you only need to find the Prufer sequence when you come across a new edge set. Also, if you actually construct the BST, you can find the Prufer sequence in linear time. Here is my python code (takes 6 seconds rather than 18).






                share|cite|improve this answer











                $endgroup$



                Is there a reason you chose to take the BST of the permutations? There are multiple ways to uniquely represent a permutation as a tree, where you would end up with $n!$ different Prufer sequences. Categorizing such sequences might be more interesting.



                But in any case, I couldn't find a way to enumerate without iterating all the $n!$ permutations. I tried to find a bijection between Prufer sequences and something counted by the difference of Catalan numbers $C_n-C_{n-1}$, but to no avail. I was however, able to speed up your code.



                Given two permutations $p_1, p_2 in S_n$



                $$ text{Prufer}(p_1) ;;;= ;;; text{Prufer}(p_2) \
                Longleftrightarrow \
                text{Tree}(p_1) ;;; = ;;; text{Tree}(p_2) \
                Longleftrightarrow \
                text{Edges}(text{BST}(p_1)) ;;; = ;;; text{Edges}(text{BST}(p_2)) \
                $$

                So you only need to find the Prufer sequence when you come across a new edge set. Also, if you actually construct the BST, you can find the Prufer sequence in linear time. Here is my python code (takes 6 seconds rather than 18).







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Jan 15 at 9:22

























                answered Jan 27 '15 at 21:27









                Andrew SzymczakAndrew Szymczak

                1,177616




                1,177616






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Mathematics Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1121288%2fidentifying-binary-search-trees-from-their-prufer-sequence%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Human spaceflight

                    Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

                    張江高科駅